Somewhat Frequent
0/14

More Applications of Segment Tree

Authors: Benjamin Qi, Andi Qu

Walking on a Segment Tree, Non-Commutative Combiner Functions

Prerequisites

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 $a_1,\ldots,a_N$ (along with point updates).

Find the first $i$ such that $a_i\ge x$.

Of course, you can do this in $\mathcal{O}(\log^2N)$ time with a max segment tree and binary searching on the first $i$ such that $\max(a_1,\ldots,a_i)\ge x$. But try to do this in $\mathcal{O}(\log N)$ time.

Solution

Problems

StatusSourceProblem NameDifficultyTags
Old GoldNormal
PlatNormal
CFNormal

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*b,a*b+b}; }
template<class T> struct BIT {
const T ID = {1,0};
int SZ = 1; V<T> x, bit;
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
CSESEasy
Show TagsPURQ
Old GoldNormal
POINormal
COCIHard
PlatHard
Show TagsGreedy, PURQ
Balkan OIHard

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!