从左往右扫,维护 2 个 max,
- 一个是
max(sub(arr[0:n]))
- 一个是
max(sub(arr[0:n], including arr[n]))
for n in arr:
max_with_n = better([n], prev_best_with_n + [n])
max_overall = better(prev_best, max_with_n)
return max_overall
例子:要求 max sum of subarray leetcode #53
原理:
arr[a:b] = arr[:b] - arr[:a]
适用: f 是线性可加的,比如 sum
例子:要求 count of subarray with sum = k leetcode #560
当你要找倒数 i 个 node, 或者中间一半/三分之一/fraction 的node, 可以用 2ptrs
例子:rotate list, 需要找倒数 i 个node
diff? max substring?
扩展(太难,见到我就投了) leetcode #137
例子:输入数据是正数,你把 nums[i]
取反,这样扫描到了第 i 个数的时候,你可以拿到本来的参数(再取反),也知道 i 在之前被标记了
leetcode 442. Find All Duplicates in an Array
例子:某种奇怪的 xor
例子:单次 pass, 扫过的空间都用过没用了,可以用来存信息
- 对邻接矩阵 A,
A[i][j]
表示是否有 i->j 的边,或者说 i->j 的长度为 1 的路线条数。 (A^2)[i][j]
表示 i->j 的长度为 2 的路线条数。(A^3)[i][j]
表示 i->j 的长度为 3 的路线条数。trace(A^3) / 6
表示 i->i 的长度为 3 的路线条数 / 6 = 图中的三角形个数。
pattern: 如果给定 List[(Interval, some_val)]
, 想要 query about aggr(f(val) for val in interval)
, 并要求可以 online 添加 interval, 可以用线段树。需要 aggr 有结合律。
例子 | interval | val | f | aggr |
---|---|---|---|---|
给定 List[int] , 求 f(i,j) = sum(List[i:j]) |
[i,i] |
arr[i] |
sum (实际没有 overlapping 所以无所谓了) |
sum |
给定 List[int] , 求 f(i,j) = min(List[i:j]) |
[i,i] |
arr[i] |
sum (实际没有 overlapping 所以无所谓了) |
min |
给定 List[Interval] , 求 max overlapping depth , 甚至 max overlapping interval |
Interval |
1 |
sum |
max |
https://leetcode.com/tag/segment-tree/
- Shuffle an array: Fisher-Yates algorithm
for i in reversed(range(len(arr))):
r = rand_int_in(range(i+1))
swap(arr[i], arr[r])
This is unbiased, forall i. forall node. P(node -> position i) = 1/n
Proof by induction.
Assume arr[:n]
is already shuffled, now extend to arr[:n+1]
. We uniformly take i
from range(n+1)
and swap arr[i]
and arr[n]
. Provable that
- P( each node go to
n
) = 1/n. - P( old
arr[n]
go to anyi
) = 1/n.
QED.
- Randomly take an element from stream: reservoir sampling
a = sample already taken from first n elements
there are 1/(n+1) chance take the new element, n/(n+1) chance keep the old (a)
Proof by induction as exercise.