Somewhat Frequent
 0/15

More Applications of Segment Tree

Authors: Benjamin Qi, Andi Qu

Walking on a Segment Tree, Non-Commutative Combiner Functions

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 a1,,aNa_1,\ldots,a_N (along with point updates).

Find the first ii such that aixa_i\ge x.

Of course, you can do this in O(log2N)\mathcal{O}(\log^2N) time with a max segment tree and binary searching on the first ii such that max(a1,,ai)x\max(a_1,\ldots,a_i)\ge x. But try to do this in O(logN)\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][l, r]. Let mid=l+r2mid = \left \lfloor{\frac{l + r}{2}}\right \rfloor.

If max(al,,amid)x\max(a_l, \dots, a_{mid}) \geq x, then we know that the answer is in the range [l,mid][l, mid]. Otherwise, the answer is in the range [mid+1,r][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(al,,ar)\max(a_l, \dots, a_r) and we know that the answer is in the range [l,r][l, r], we move to the left child if max(al,,amid)x\max(a_l, \dots, a_{mid}) \geq x; otherwise, we move to the right child.

This is convenient because max(al,,amid)\max(a_l, \dots, a_{mid}) is already stored in the left child, so we can find it in O(1)\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

StatusSourceProblem NameDifficultyTags
Old GoldNormal
CFNormal

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][l, r] we store the following information:

  • The maximum subarray sum in the range [l,r][l, r]. (Let this be GG)
  • The maximum subarray sum in the range [l,r][l, r] if it must contain ala_l. (Let this be LL)
  • The maximum subarray sum in the range [l,r][l, r] if it must contain ara_r. (Let this be RR)
  • The total sum of the range. (Let this be SS)

When we combine two nodes uu (left child) and vv (right child) to make node ww,

  • w.G=max(u.G,v.G,u.R+v.L)w.G = \max(u.G, v.G, u.R + v.L)
  • w.L=max(u.L,u.S+v.L)w.L = \max(u.L, u.S + v.L)
  • w.R=max(u.R+v.S,v.R)w.R = \max(u.R + v.S, v.R)
  • w.S=u.S+v.Sw.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),

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Old GoldEasy
CSESEasy
Show TagsPURQ
CFEasy
Show TagsPURQ
Old GoldNormal
POINormal
PlatinumNormal
Show TagsMatrix, PURQ
COCIHard
Show TagsPURQ
PlatinumHard
Show TagsGreedy, PURQ
Balkan OIHard

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!