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

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.

Problems