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 (along with point updates).
Find the first such that .
Of course, you can do this in time with a max segment tree and binary searching on the first such that . But try to do this in 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 . Let .
If , then we know that the answer is in the range . Otherwise, the answer is in the range .
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 and we know that the answer is in the range , we move to the left child if ; otherwise, we move to the right child.
This is convenient because is already stored in the left child, so we can find it in 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 we store the following information:
- The maximum subarray sum in the range . (Let this be )
- The maximum subarray sum in the range if it must contain . (Let this be )
- The maximum subarray sum in the range if it must contain . (Let this be )
- The total sum of the range. (Let this be )
When we combine two nodes (left child) and (right child) to make node ,
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!