Somewhat Frequent

More Applications of Segment Tree

Authors: Benjamin Qi, Andi Qu

Walking on a Segment Tree, Non-Commutative Combiner Functions


both of these topics


Includes 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)\mathcal{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)\mathcal{O}(\log N) time.

Solution - Hotel Queries



StatusSourceProblem NameDifficultyTags
Old GoldNormal

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.

using T = AR<mi,2>;
T comb(const T& a, const T& b) { return {a[0]*b[0],a[1]*b[0]+b[1]}; }
template<class T> struct BIT {
const T ID = {1,0};
int SZ = 1; V<T> x, bit[2];
void init(int N) {
while (SZ <= N) SZ *= 2;
x = V<T>(SZ+1,ID); F0R(i,2) bit[i] = x;
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.



StatusSourceProblem NameDifficultyTags
Old GoldEasy
Old GoldNormal
Show Tags
Show TagsGreedy, PURQ
Balkan OIHard

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!