Segment Tree Flashcards
Dynamic Range Minimum Query
* Add(i, v) A[i] += v
* RMQ(i, j) returns the position of the minimum element in A[i, …, j]
Solution with Segment Tree
Store in each node the minimum element of the segment and its position
Dynamic RMQ with occurrences
* Add(i, v) A[i] += v
* Query(i, j) returns the position of the minimum element in A[i, …, j] and its number of occurrences
Solution with Segment Tree
Store in each node the minimum element of the segment and its number of occurrences
Shortest prefix higher than a value
* Add(i, v) A[i] += v
* Query(s) search for the shortest prefix of A, say i, such that the sum of the elements A[1, …, i] is higher than s
Solution with Segment Tree
Store in each node the sum of the elements of the segment.
For each node, if value v at left child >= s, go left, otherwise s -= v and go right
Position of the k-th 0
Given binary array A[0, n-1]
* Add(i, v) A[i] += v
* Select(k) reports the position of the k-th occurrence of 0
Solution with Segment Tree
Store in each node the number of zeroes in the segment.
For each node, if value v at left child >= k, go left, otherwise k -= v and go right
Position of the k-th 0 in subarray A[i, …, j]
Given binary array A[0, n-1]
* Add(i, v) A[i] += v
* SelectHard(i, j, k) reports the position of the k-th occurrence of 0 in subarray A[i, …, j]
Solution with Segment Tree
Note: SelectHard is equal to Select(k + Sum(i-1)) where Sum(i-1) is the number of 0 in the prefix A[0, i-1]
Store in each node the number of zeroes in the segment.
For each node, if value v at left child >= k, go left, otherwise k -= v and go right
Number of occurrences of X in subarray A[i, …, j]
Given array A[0, n-1]
* Add(i, v) A[i] += v
* Occs(i, j, x) reports number of occurrences of x in subarray A[i, …, j]
Solution with Segment Tree
Store in each node the set of distinct values in the segment with their number of occurrences.
You can use BBST, so for logn node we spend Θ(logn) time for each note then Θ(log^2 n) is the overall time
Space complexity: every value of A is stored in at most logn nodes. Overall space is nlogn
Successor in subarray A[i, …, j]
Given array A[0, n-1]
* Add(i, v) A[i] += v
* Succ(i, j, x) reports the successor of x in subarray A[i, …, j]
Solution with Segment Tree
Store in each node a BBST with the set of distinct values in the segment. The answer is the min of the successor in each totally overlapping nodes.
Θ(log^2 n) query time. Can be improved with Fractional Cascading but it is not needed for the exam
k-th smallest element in subarray A[i, …, j]
Given (static) array A[0, n-1]
* Add(i, v) A[i] += v
* Smallest(i, j, k) reports the k-th smallest element in subarray A[i, …, j]
Solution with Segment Tree
Solve a easier query: Smallest(0, j, k) reports the k-th smallest in a prefix.
Assume values are in [0, n-1], if not remap.
Store in STj the occurrences of all the appearing numbers in A[0, j] then perform Smallest(0, j, k) on STj (search the position where prefix sum is greater than k).
Because we need n segment trees, use persistency by adding the occurrence of value A[j] at time j.
The general Smallest(i, j, k) query would need STij. Each node Uij of STij can be computed on-the-fly with the node Ui from STi and the node Uj from STj:Uij = Uj - Ui
Θ(nlogn) space
Θ(logn) query time
Triplets
Given A[0, n-1] with positive integers < n, count the number of triplets i,j,k (0 <=i < j < k <= n-1) such that
A[i] < A[j] < A[k]
Solution with Segment Tree
Assume values are in [0, n-1], if not remap.
Use two STs, one for the prefix and one for the suffix. STprefix is initialized to 0. Stsuffix is initialized to 1 in position A[i] for all i.
For all j
* RangeSum(A[j], n) on STsuffix gives the number of elements greater than A[j] and in pos k > j
* RangeSum(0, A[j]) on STprefix gives the number of elements lower than A[j] and in pos i < j
* Set to 1 the position j in STprefix and set to 0 the position j in STsuffix
Θ(nlogn) query time
Smaller value
Given A[0, n-1] positive integers < n. Solve m given count queries (offline)
* count(i, j, X) reports the number of k (i <= k <= j) such that A[k] <= X
Use persistent segment tree.
Process values of A in sorted order.
If A[k] = t, then set B[k]=1 at time t
count(i, j, X) = RangeSum(i, j) at time X
Θ((n+m)logn) query time
Lazy Propagation
To update an interval we will keep 3 things in mind.
- If current segment tree node has any pending update, then first add that pending update to current node.
- If the interval represented by current node lies completely in the interval to update, then update the current node and update the lazy[] array for children nodes.
- If the interval represented by current node overlaps with the interval to update, then update the nodes as the earlier update function
Cases while updating:
1. Segment lies outside the query range: in this case, we can just simply return back and terminate the call.
2. Segment lies fully inside the query range: in this case, we simply update the current node and mark the children lazy.
3. If they intersect partially, then we all update for both the child and change the values in them.
Persistent Segment Tree
