PrevNext
Somewhat Frequent
 0/12

More Applications of Segment Tree

Authors: Benjamin Qi, Andi Qu

Walking on a Segment Tree, Non-Commutative Combiner Functions

Resources
CF

both of these topics

cp-algo

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

Solution

Problems

StatusSourceProblem NameDifficultyTags
Old GoldNormal
PlatNormal

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 NameDifficultyTags
CSESEasy
Old GoldEasy
Old GoldNormal
POINormal
COCIHard
Show Tags
PlatHard
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!

PrevNext