Segment Tree Beats
Segment Tree Beats is an advanced version of lazy segment tree. We use it when a range update is sometimes easy to apply to a whole segment, but sometimes the segment is too mixed and we must go deeper.
In this lecture, we study one of the classic Segment Tree Beats tasks: range , range , and range sum query.
Here means:
For every in , replace with .
And means:
For every in , replace with .
So one update caps values from above, and the other update raises values from below. A normal lazy segment tree is not enough, because these updates do not affect all elements in the same way. Some values change, and some values stay the same.
We have an array . We need to process three types of queries:
1 l r x: for every in , set ;2 l r x: for every in , set ;3 l r: print the sum .For every segment tree node, we store information about both ends of the values in the segment.
For the maximum side, we store:
For the minimum side, we store:
We also store:
The maximum side is used for . If we apply and , then only the maximum values change. All other values are at most , so they are already smaller than .
So we can update the whole node immediately:
The minimum side is symmetric and is used for . If we apply and , then only the minimum values change. All other values are at least , so they are already larger than .
So we can update the whole node immediately:
This is the main idea of Segment Tree Beats: update the node directly when the update crosses only the extreme group. If the update crosses deeper into the segment, go down to the children.
The recursive structure is the same as in a normal segment tree. Each function receives the current node , the segment , and the part of the query range that lies inside it.
The main decision is simple: when an update reaches a node, first try to finish at this node. We go deeper only if the update changes more than one value group and the node does not store enough information to update itself safely.
The time improvement comes from stopping many updates at high nodes. A single update may still go down several branches, but the Segment Tree Beats analysis shows that this cannot happen too often across many operations.
Algorithm:
At first, Segment Tree Beats looks risky. In a normal lazy segment tree, if a node is fully inside the update range, we usually stop there. In Segment Tree Beats, this is not always possible. Sometimes the node is fully inside the range, but the update is not safe, so we still have to go to its children. So why is it still fast?
We use a potential idea. For every segment tree node , define the number of different values inside the segment of . Now define the total potential:
At the beginning, is at most , because every array element belongs to segment tree nodes. So, if we count values over all nodes, the total amount is .
Now let us look at a hard case. For , a fully covered node has three cases:
The third case is the only extra work. But if , then at least two different value levels are affected: the maximum level and the second maximum level. After applying , these levels become merged. So decreases by at least . That means:
Every time we enter the hard case for , the total potential decreases by at least .
The same argument works for . Now we need to understand how can increase.
A full safe update does not create many new values. It only changes one extreme group inside a node. The only places where new different values can appear are near the usual boundary nodes of the range . There are only such nodes in a segment tree operation. So each operation can increase by only .
Therefore, over all operations:
So the total number of hard cases over all operations is controlled by the potential.
1. Build the segment tree.
1. If l == r, create a leaf node from a[l].
2. Otherwise build the left child and the right child.
3. Pull the current node from its children.
2. To process chmin(l, r, y):
1. Call upd_min(1, 1, n, l, r, y).
2. If the current query part is empty, return.
3. If mx <= y, return.
4. If l == tl && r == tr && smx < y:
- only the maximum group changes;
- apply chmin(y) to this node;
- return.
5. Push the current node to its children.
6. Recurse into the left child with [tl, min(m, tr)].
7. Recurse into the right child with [max(m + 1, tl), tr].
8. Pull the current node.
3. To process chmax(l, r, y):
1. Call upd_max(1, 1, n, l, r, y).
2. If the current query part is empty, return.
3. If mn >= y, return.
4. If l == tl && r == tr && smn > y:
- only the minimum group changes;
- apply chmax(y) to this node;
- return.
5. Push the current node to its children.
6. Recurse into the left child with [tl, min(m, tr)].
7. Recurse into the right child with [max(m + 1, tl), tr].
8. Pull the current node.
4. To process sum(l, r):
1. Call get_sum(1, 1, n, l, r).
2. If the current query part is empty, return 0.
3. If l == tl && r == tr, return sum.
4. Push the current node to its children.
5. Return the sum of the answers from the left and right children.
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5;
const long long INF = (1LL << 60);
int n, q;
long long a[N];
struct Node {
long long sum;
long long mx;
long long smx;
int cmx;
long long mn;
long long smn;
int cmn;
Node() {}
Node(long long x) {
sum = x;
mx = x;
smx = -INF;
cmx = 1;
mn = x;
smn = INF;
cmn = 1;
}
};
Node t[4 * N];
Node comb(const Node &L, const Node &R) {
Node cur;
cur.sum = L.sum + R.sum;
if (L.mx == R.mx) {
cur.mx = L.mx;
cur.cmx = L.cmx + R.cmx;
cur.smx = max(L.smx, R.smx);
} else if (L.mx > R.mx) {
cur.mx = L.mx;
cur.cmx = L.cmx;
cur.smx = max(L.smx, R.mx);
} else {
cur.mx = R.mx;
cur.cmx = R.cmx;
cur.smx = max(L.mx, R.smx);
}
if (L.mn == R.mn) {
cur.mn = L.mn;
cur.cmn = L.cmn + R.cmn;
cur.smn = min(L.smn, R.smn);
} else if (L.mn < R.mn) {
cur.mn = L.mn;
cur.cmn = L.cmn;
cur.smn = min(L.smn, R.mn);
} else {
cur.mn = R.mn;
cur.cmn = R.cmn;
cur.smn = min(L.mn, R.smn);
}
return cur;
}
void pull(int x) {
t[x] = comb(t[x * 2], t[x * 2 + 1]);
}
void apply_chmin(int x, long long y) {
if (t[x].mx <= y) {
return;
}
long long old_mx = t[x].mx;
t[x].sum -= 1ll * (old_mx - y) * t[x].cmx;
if (t[x].mn == old_mx) {
t[x].mn = y;
} else if (t[x].smn == old_mx) {
t[x].smn = y;
}
t[x].mx = y;
}
void apply_chmax(int x, long long y) {
if (t[x].mn >= y) {
return;
}
long long old_mn = t[x].mn;
t[x].sum += 1ll * (y - old_mn) * t[x].cmn;
if (t[x].mx == old_mn) {
t[x].mx = y;
} else if (t[x].smx == old_mn) {
t[x].smx = y;
}
t[x].mn = y;
}
void push(int x) {
apply_chmin(x * 2, t[x].mx);
apply_chmin(x * 2 + 1, t[x].mx);
apply_chmax(x * 2, t[x].mn);
apply_chmax(x * 2 + 1, t[x].mn);
}
void build(int x, int l, int r) {
if (l == r) {
t[x] = Node(a[l]);
return;
}
int m = (l + r) / 2;
build(x * 2, l, m);
build(x * 2 + 1, m + 1, r);
pull(x);
}
void upd_min(int x, int l, int r, int tl, int tr, long long y) {
if (tl > tr || t[x].mx <= y) {
return;
}
if (l == tl && r == tr && t[x].smx < y) {
apply_chmin(x, y);
return;
}
push(x);
int m = (l + r) / 2;
upd_min(x * 2, l, m, tl, min(m, tr), y);
upd_min(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, y);
pull(x);
}
void upd_max(int x, int l, int r, int tl, int tr, long long y) {
if (tl > tr || t[x].mn >= y) {
return;
}
if (l == tl && r == tr && t[x].smn > y) {
apply_chmax(x, y);
return;
}
push(x);
int m = (l + r) / 2;
upd_max(x * 2, l, m, tl, min(m, tr), y);
upd_max(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, y);
pull(x);
}
long long get_sum(int x, int l, int r, int tl, int tr) {
if (tl > tr) {
return 0;
}
if (l == tl && r == tr) {
return t[x].sum;
}
push(x);
int m = (l + r) / 2;
return get_sum(x * 2, l, m, tl, min(m, tr)) +
get_sum(x * 2 + 1, m + 1, r, max(m + 1, tl), tr);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
while (q--) {
int type;
cin >> type;
if (type == 1) {
int l, r;
long long x;
cin >> l >> r >> x;
upd_min(1, 1, n, l, r, x);
} else if (type == 2) {
int l, r;
long long x;
cin >> l >> r >> x;
upd_max(1, 1, n, l, r, x);
} else {
int l, r;
cin >> l >> r;
cout << get_sum(1, 1, n, l, r) << '\n';
}
}
return 0;
}