# More Applications of Segment Tree

Authors: Benjamin Qi, Andi Qu

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.

#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];

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