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

Non-Commutative Combiner Functions

Solution - Subarray Sum Queries

Problems