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 (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
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Old Gold | Normal | ||||
Plat | Normal | ||||
CF | Normal |
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
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CSES | Easy | ||||
Old Gold | Easy | ||||
CSES | Easy | Show TagsPURQ | |||
Old Gold | Normal | ||||
POI | Normal | ||||
COCI | Hard | ||||
Plat | Hard | Show TagsGreedy, PURQ | |||
Balkan OI | Hard |