PrevNext
Rare
 0/10

Segment Tree Beats

Authors: Benjamin Qi, Dustin Miao

Perform chmin and chmax range updates

Segment Tree Beats

Focus Problem – read through this problem before continuing!

Solution - The Child and Sequence

First consider a lazy segment tree. A pseudocode for the update function looks something like:

function update(upd_left, upd_right, upd_value, tree_node, tree_left, tree_right)
	if upd_right < tree_left or tree_right < upd_left
		return
	if upd_left ≤ tree_left and tree_right ≤ upd_right
		apply update
		return
	push lazy updates down

	let tree_mid = (tree_left + tree_right) / 2
	let left_child = 2 * tree_node
	let right_child = 2 * tree_node + 1
	update(upd_left, upd_right, upd_value, left_child, tree_left, tree_mid)
	update(upd_left, upd_right, upd_value, right_child, tree_mid + 1, tree_right)
	merge values from children

At first, this problem may seem like an ordinary lazy segment tree problem, but the range modulo updates prevent updates from stacking. That is, for a given node, it is difficult to calculate what the sum value of the node will be after an update. Furthermore, in the lazy array, modulo, unlike sum, does not satisfy xmodamodb=xmod(a+b)x \mod a \mod b = x \mod (a + b) or any other simple identity. How do we get around this?

As it turns out, we can take advantage of an important property of modulo. Modulo either does not affect a number, or decreases it by at least half of what it was. If the number in question is xx, and the modulo was by mm, then this can be proved using casework:

  • If m>xm > x, then xx is unaffected by mm
  • If mx/2m \le x / 2, then after the modulo operation xx must be strictly less than mm
  • If x/2<mxx / 2 < m \leq x, then xmodm=xmx \mod m = x - m. This then reduces to the second case.

Let us ignore operations of type 3 for the time being. Because of this property of modulo, an element with value aa will get decreased at most loga\lceil \log a \rceil times (although a greater number of updates may not affect the element). Taking this into account, we can slightly modify the modulo update function to encorporate these optimizations.

function update(upd_left, upd_right, upd_value, tree_node, tree_left, tree_right)
	let cur_max = the maximum element in [tree_left, tree_right]

	if upd_right < tree_left or tree_right < upd_left or cur_max < upd_value
		return
	if upd_left = upd_right
		apply update
		return

	let tree_mid = (tree_left + tree_right) / 2
	let left_child = 2 * tree_node
	let right_child = 2 * tree_node + 1
	update(upd_left, upd_right, upd_value, left_child, tree_left, tree_mid)
	update(upd_left, upd_right, upd_value, right_child, tree_mid + 1, tree_right)
	merge values from children

Note: Because we are no longer doing range updates with lazy propogation, there is no need for a lazy tag.

We will store cur_max\texttt{cur\_max} in a seperate array as a seperate (mergable) value. Although it is possible that a single query processes O(n)\mathcal{O}(n) nodes, over all queries this amortizes to the acceptable time complexity of O((n+q)loga)\mathcal{O}((n + q)\log a).

Consider adding in operations of type 3. Although the implementation is relatively straightforward (simply a point update on segment tree), the proof of complexity from the previous section falls apart because elements can be increased back to their maximum value.

Define the entropy of the array to be k=1nlogak\sum_{k = 1}^n \lceil \log a_k \rceil, or equivalently, the maximum number of modulo operations to decrease the array to its base state of all 0s. Note that each update operation runs in Ω(logn)\mathcal{\Omega}(\log n), so if there are no point updates, then the time complexity is O(nlogalogn)\mathcal{O}(n \log a \log n). Each point update increases the entropy by a fixed amount loga\lceil \log a \rceil. If there are qpq_p point updates, then the total entropy over all updates is bounded by nloga+qplogan \log a + q_p \log a. If we factor out these point update operations, each modulo update is still bounded by the total entropy. This means that even with point updates, our solution still runs in O(nlogalogn+qploga)=O((n+q)lognloga)\mathcal{O}(n \log a \log n + q_p \log a) = \mathcal{O}((n + q)\log n \log a).

Although strictly speaking, The Child and Sequence is not a segment tree beats problem, the techniques used in it are closely related. In short, segment tree beats is a technique that allows a non-polylogarithmic range update complexity that amortizes to O(nlogn)\mathcal{O}(n \log n) or O(nlog2n)\mathcal{O}(n \log^2 n).

Implementation - The Child and Sequence

C++

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
int N, Q;
long long tsum[MAXN * 4], tmax[MAXN * 4];
void update_mod(int l, int r, long long v, int t = 1, int tl = 1, int tr = N) {
if (r < tl || tr < l || tmax[t] < v) {

Focus Problem – read through this problem before continuing!

Solution - Range Chmin Chmax Add Set Sum

The solution to The Child and Sequence uses a simplified but similar solution to segment tree beats. For the problem above, let us divide it into three subtasks:

  1. Allow only operations 0 and 3
  2. Allow only operations 0, 2, and 3
  3. All operations are allowed

Subtask 1

Build a segment tree over the range. In each node of the segment tree, maintain four values: sum\texttt{sum}, max1\texttt{max}_1, max2\texttt{max}_2, and maxc\texttt{max}_c, which correspond respectively to the sum of the elements of said range, the strict maximum value, the strict second largest value (if there is no such value, -\infty), and the number of occurences of the maximum element. We would like to perform the following operations:

  • For each i[l,r]i \in [l, r], let A[i]=min(A[i],x)A[i] = \min(A[i], x) (this operation will henceforth be referred as chmin)
  • Query i=lrA[i]\sum_{i = l}^r A[i]

The issue, again, is that in lazy propogation, it is difficult to update the sum to reflect the chmin update. We will use a similar strategy to the previous task where we build a seemingly slow solution, and then optimize it to pass in time.

Firstly, if the update value is larger than the maximum value in the range (stored in max1\texttt{max}_1), then we can return as the update will not effect any element in the range. Secondly, if the update value is between max1\texttt{max}_1 and max2\texttt{max}_2, the new sum can be easily calculated using maxc\texttt{max}_c.

function update(upd_left, upd_right, upd_value, tree_node, tree_left, tree_right)
	if upd_right < tree_left or tree_right < query_left or max1 < upd_value
		return
	if query_left < tree_left and tree_right < query_right and max2 < upd_value
		apply update
		return
	push lazy updates down

	let tree_mid = (tree_left + tree_right) / 2
	let left_child = 2 * tree_node
	let right_child = 2 * tree_node + 1
	update(upd_left, upd_right, upd_value, left_child, tree_left, tree_mid)
	update(upd_left, upd_right, upd_value, right_child, tree_mid + 1, tree_right)
	merge values from children

To prove that this runs in O((n+q)logn)\mathcal{O}((n + q) \log n), we need to define a variable δ\delta that represents the sum of the number of distinct elements over all intervals in the segment tree. This number is bounded by nlognn \log n, which is the sum of the sizes of every interval.

Why are queries slow? Because they could visit up to nn nodes in any given query. Define an extra operation to be when a query is passed onto a node's children dispite being in the query range. In other words, when a node satisfies query_left ≤ tree_left and tree_right ≤ query_right and upd_value ≤ max2, an extra operation is performed.

Each time an extra operation is performed, δ\delta decreases by at least 1, because both the max1\texttt{max}_1 and max2\texttt{max}_2 elements are decreased to xx. Because δ\delta does not increase, the complexity is bounded by maxδ=O(nlogn)\max \delta = \mathcal{O}(n \log n).

Subtask 2

Sum range updates can be added without much modification to the existing code, by simply adding another lazy tag. The proof of the time complexity from the previous part breaks down, but a tentative upper bound of the algorithm is O((n+q)log2n)\mathcal{O}((n + q) \log^2 n). A complete proof can be found here.

Subtask 3

Store three more variables min1\texttt{min}_1, min2\texttt{min}_2, and minc\texttt{min}_c. These will be implemented similar to their max\texttt{max} counterparts. Take note of the edge case when min1=max2\texttt{min}_1 = \texttt{max}_2 or vice versa.

Implementation - Range Chmin Chmax Add Range Sum

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200001; // 1-based
int N;
ll A[MAXN];
struct Node {

Problems

StatusSourceProblem NameDifficultyTags
HDUVery Easy
Show TagsSegTreeBeats
CSAEasy
Show TagsSegTreeBeats
CFNormal
Show TagsSegTreeBeats
HRNormal
Show TagsSegTreeBeats
CFNormal
Show TagsSegTreeBeats
CFNormal
Show TagsSegTreeBeats
CFNormal
Show TagsSegTreeBeats
CFHard
Show TagsSegTreeBeats

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!

PrevNext