More Applications of Segment Tree

Walking on a Segment Tree

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})$

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

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})$

Copy
#include <bits/stdc++.h>
using namespace std;

template <class T> class SumSegmentTree {
  private:
	const T DEFAULT = 0;

	int len;
	vector<T> segtree;

Problems

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.

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.

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

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