# More Applications of Segment Tree

Authors: Benjamin Qi, Andi Qu

### Prerequisites

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 $a_{1},…,a_{N}$ (along with point updates).

Find the first $i$ such that $a_{i}≥x$.

Of course, you can do this in $O(g_{2}N)$ time with a max segment tree and binary searching on the first $i$ such that $max(a_{1},…,a_{i})≥x$. But try to do this in $O(gN)$ time.

### Solution - Hotel Queries

Solution

### Problems

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

Old Gold | Normal | External Sol | ||||

Plat | Normal | External 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

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

Old Gold | Easy | External Sol | ||||

Old Gold | Normal | External Sol | ||||

POI | Normal | View Solution | ||||

Plat | Hard | ## Show TagsPURQ, Greedy | External Sol | |||

Balkan OI | Hard |

### 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.