# More Applications of Segment Tree

Authors: Benjamin Qi, Andi Qu, Justin Ji

Walking on a Segment Tree, Non-Commutative Combiner Functions

### Prerequisites

Resources | ||||
---|---|---|---|---|

CF EDU | both of these topics | |||

cp-algo | Includes these two applications and more. |

## Walking on a Segment Tree

Focus Problem – try your best to solve 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 - Hotel Queries

Instead of binary searching and querying the segment tree separately, let's do them together!

Assume that you know that the answer is in some range $[l, r]$. Let $mid = \left \lfloor{\frac{l + r}{2}}\right \rfloor$.

If $\max(a_l, \dots, a_{mid}) \geq x$, then we know that the answer is in the range $[l, mid]$. Otherwise, the answer is in the range $[mid + 1, r]$.

Imagine that the segment tree is a decision tree. We start at the root and move down. When we're at some node that contains $\max(a_l, \dots, a_r)$ and we know that the answer is in the range $[l, r]$, we move to the left child if $\max(a_l, \dots, a_{mid}) \geq x$; otherwise, we move to the right child.

This is convenient because $\max(a_l, \dots, a_{mid})$ is already stored in the left child, so we can find it in $\mathcal{O}(1)$ time.

**Time Complexity:** $\mathcal{O}(N + Q\log{N})$

C++

#include <bits/stdc++.h>using namespace std;const int MAXN = 200001;int n;int segtree[4 * MAXN], a[MAXN];void build(int l = 1, int r = n, int node = 1) {if (l == r) segtree[node] = a[l];

Focus Problem – try your best to solve this problem before continuing!

### Solution - Ordered Set

First, we coordinate compress all the values, and keep track of the frequency of each value in the array we build our segment tree on. We can answer the $\texttt{INSERT}$, $\texttt{DELETE}$, and $\texttt{COUNT}$ queries using the sum segment tree from the PURS module. Answering the $\texttt{K-TH}$ queries in $\mathcal{O}(\log{N})$ time requires us to use segment tree walking.

Let $\texttt{freq}[i]$ equal the number of times $i$ occurs in our set. In our array of coordinate compressed values, we want to find the first index $x$ such that $\sum_{i=0}^{x} \texttt{freq}[i]$ is $\geq K$.

In the previous problem, we were walking on the prefix maximum of our array. Here, we are walking on the prefix sum of our array. The difference here is that if we know our answer is in $[l, r]$, then checking the maximum in our left and right children is enough to know if we should walk left or right. But with sum, we also need to consider the range $[1, l)$ and how it might affect our answer.

To keep track of the prefix $[1, l)$, we first set our prefix result to be a neutral value. By neutral value, we mean the identity of the operation (for addition it's 0, for multiplication it's 1, etc.). Every time we walk right, we add the left child's value to our prefix result.

**Time Complexity:** $\mathcal{O}(Q\log{Q})$

C++

#include <bits/stdc++.h>using namespace std;template <class T> class SumSegmentTree {private:const T DEFAULT = 0;int len;vector<T> segtree;

### Problems

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

Old Gold | 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 – try your best to solve this problem before continuing!

Focus Problem – try your best to solve 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);

### Solution - Subarray Sum Queries

Hint: In each node of the segment tree, you'll need to store four pieces of information.

In each node of the segment tree that stores information about the range $[l, r]$ we store the following information:

- The maximum subarray sum in the range $[l, r]$. (Let this be $G$)
- The maximum subarray sum in the range $[l, r]$ if it must contain $a_l$. (Let this be $L$)
- The maximum subarray sum in the range $[l, r]$ if it must contain $a_r$. (Let this be $R$)
- The total sum of the range. (Let this be $S$)

When we combine two nodes $u$ (left child) and $v$ (right child) to make node $w$,

- $w.G = \max(u.G, v.G, u.R + v.L)$
- $w.L = \max(u.L, u.S + v.L)$
- $w.R = \max(u.R + v.S, v.R)$
- $w.S = u.S + v.S$

We can thus handle updates and queries efficiently.

#include <bits/stdc++.h>typedef long long ll;using namespace std;const ll MAXN = 200001;struct Node {ll g_max, l_max, r_max, sum;Node operator+(Node b) {return {max(max(g_max, b.g_max), r_max + b.l_max), max(l_max, sum + b.l_max),

### Problems

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

CSES | Easy | ||||

Old Gold | Easy | ||||

CSES | Easy | ## Show TagsPURQ | |||

CF | Easy | ## Show TagsPURQ | |||

Old Gold | Normal | ||||

POI | Normal | ||||

Platinum | Normal | ## Show TagsMatrix, PURQ | |||

COCI | Hard | ## Show TagsPURQ | |||

Platinum | Hard | ## Show TagsGreedy, PURQ | |||

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!