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
CFboth of these topics
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 (along with point updates).

Find the first such that .

Of course, you can do this in time with a max segment tree and binary searching on the first such that . But try to do this in time.

Solution - Hotel Queries

Solution

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
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.

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.

Solution

Problems

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

PURQ, Greedy

External Sol
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!

Give Us Feedback on More Applications of Segment Tree!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext