PrevNext
Somewhat Frequent
 0/10

More Applications of Segment Tree

Authors: Benjamin Qi, Andi Qu

Walking on a Segment Tree, Non-Commutative Combiner Functions

Resources
cp-algoIncludes these two applications and more.

Walking on a Segment Tree

Focus Problem – read through this problem before continuing!

You want to support queries of the following form on an array a1,,aNa_1,\ldots,a_N (along with point updates).

Find the first ii such that aixa_i\ge x.

Of course, you can do this in O(log2N)O(\log^2N) time with a max segment tree and binary searching on the first ii such that max(a1,,ai)x\max(a_1,\ldots,a_i)\ge x. But try to do this in O(logN)O(\log N) time.

Solution - Hotel Queries

Solution

Problems

StatusSourceProblem NameDifficultyTagsSolution
Old GoldNormalExternal Sol
PlatNormalExternal Sol

Non-Commutative Combiner Functions

Previously, we only considered commutative operations like + and max. However, segment trees allow you to answer range queries for any associative operation.

Focus Problem – read through this problem before continuing!

Focus Problem – read through this problem before continuing!

Solution - Point Set Range Composite

The segment tree from the prerequisite module should suffice. You can also use two BITs as described here, although it's more complicated.

1using T = AR<mi,2>;
2T comb(const T& a, const T& b) { return {a[0]*b[0],a[1]*b[0]+b[1]}; }
3
4template<class T> struct BIT {
5 const T ID = {1,0};
6 int SZ = 1; V<T> x, bit[2];
7 void init(int N) {
8 while (SZ <= N) SZ *= 2;
9 x = V<T>(SZ+1,ID); F0R(i,2) bit[i] = x;
10 FOR(i,1,N+1) re(x[i]);

Solution - Subarray Sum Queries

Hint: In each node of the segment tree, you'll need to store four pieces of information.

Solution

Problems

StatusSourceProblem NameDifficultyTagsSolution
Old GoldEasyExternal Sol
Old GoldNormalExternal Sol
POINormalView Solution
PlatHard
Show Tags

PURQ, Greedy

External Sol
Balkan OIHard

Module Progress:

Give Us Feedback on More Applications of Segment Tree!

PrevNext