Data

Structures II

Range Trees
over Trees

Range
Updates,
Data Structures II
Point Queries
COMP4128 Programming Challenges
Range
Updates,
Range Queries

Range Trees
of Data
Structures
School of Computer Science and Engineering
Solving
Problems in UNSW Sydney
Subranges

Searching a
Range Tree Term 3, 2022
 Table of Contents 2

Data
Structures II

Range Trees
1 Range Trees over Trees
over Trees

Range
Updates, 2 Range Updates, Point Queries
Point Queries

Range
Updates, 3 Range Updates, Range Queries
Range Queries

Range Trees
of Data
Structures
4 Range Trees of Data Structures
Solving
Problems in
Subranges
5 Solving Problems in Subranges
Searching a
Range Tree
6 Searching a Range Tree
 Range Tree on Trees 3

Data
Structures II

Range Trees
over Trees
For this section, assume all trees are rooted with a
Range
specified root.
Updates,
Point Queries

Range
Updates,
Range Queries We’ve seen how to do certain path queries using the LCA
Range Trees data structure.
of Data
Structures

Solving
Problems in
Subranges
Another natural and useful question is how to do subtree
Searching a
Range Tree queries/updates.
 Range Tree on Trees 4

Data
Structures II
Problem Statement Given a tree rooted at node 0, each
node has a value, all values are initially 0. Support the
Range Trees
over Trees
following 2 operations.
Range
Update: Of the form U i w. Change the value of node i to
Updates, i.
Point Queries
Query: Of the form Q i. What is the sum of values in the
Range
Updates, subtree rooted at vertex i?
Range Queries

Range Trees
of Data
Input First line, n, q, number of vertices and operations.
Structures 1 ≤ n, q ≤ 100, 000. The next line specifies the tree. n − 1
Solving
Problems in
integers, pi , the parent of vertex i (1-indexed).
Subranges
The following q lines describe the updates and queries.
Searching a
Range Tree 1 ≤ n, q ≤ 100, 000.

Output For each Query, an integer, the sum of values in

the subtree rooted at ai .
 Range Tree on Trees 5

Data
Structures II 0

Range Trees
over Trees

Range 1 4
Updates,
Point Queries

Range
Updates,
Range Queries 2 3
Range Trees
of Data
Structures
Sample Input: Sample Output:
Solving
Problems in
Subranges U 3 1 3
Searching a U 4 2 1
Range Tree
Q 0 4
Q 1
U 4 3
Q 0
 Range Tree on Trees 6

Data
Structures II

To support general subtree queries, we will extend our

Range Trees
over Trees
range trees to work on trees.
Range
Updates,
Point Queries The key here is to find an ordering of the vertices such
Range
Updates,
that every subtree corresponds to a range of indices.
Range Queries

Range Trees
of Data Actually, any sensible DFS ordering already does this.
Structures

Solving
Problems in
Subranges DFS processes all nodes in a subtree before returning from
Searching a the subtree. So as long as we’re assigning ids
Range Tree
consecutively, a whole subtree should get consecutive
indices.
 Range Tree on Trees 7

Data
Structures II Implementation: In your DFS that creates a
representation of the tree, also either preorder or postorder
Range Trees
over Trees
the vertices. Each node should store the range of indices
Range that exists in its subtree.
Updates,
Point Queries Now build your range tree over these indices. Past this
Range
Updates,
point, you can forget about your tree and just work on
Range Queries your array of indices.
Range Trees
of Data To update node u, look up what its index is. Then just
Structures
update your range tree at indexInRangeTree[u].
Solving
Problems in
Subranges To query a subtree rooted at v, look up the range of
Searching a indices in its subtree. Then just query your range tree for
Range Tree
the range [startRange[v], endRange[v]).
Moral: Queries on subtrees are essentially the same as
just normal range queries.
 Range Tree on Trees 8

Data
Structures II #include <vector >
using namespace std;

const int N = 100100;

Range Trees // Suppose you already have your tree set up.
over Trees vector <int > children [N];
// A node is responsible for the range [ startRange [v], endRange [v])
Range int indexInRangeTree [N], startRange [N], endRange [N];
Updates, int totId;
Point Queries // A range tree that supports point update , range sum queries .
long long rangeTree [1<<18];
Range
void update(int plc , int v);
Updates,
long long query(int qL , int qR); // Query for [qL , qR)
Range Queries

Range Trees void compute_tree_ranges (int c) {

of Data indexInRangeTree [c] = startRange [c] = totId ++;
Structures for (int nxt : children [c]) {
compute_tree_ranges (nxt);
Solving }
Problems in endRange [c] = totId;
Subranges }

Searching a void update_node (int id , int v) {

Range Tree update( indexInRangeTree [id], v);
}

int query_subtree (int id) {

return query( startRange [id], endRange [id]);
}
 Table of Contents 9

Data
Structures II

Range Trees
1 Range Trees over Trees
over Trees

Range
Updates, 2 Range Updates, Point Queries
Point Queries

Range
Updates, 3 Range Updates, Range Queries
Range Queries

Range Trees
of Data
Structures
4 Range Trees of Data Structures
Solving
Problems in
Subranges
5 Solving Problems in Subranges
Searching a
Range Tree
6 Searching a Range Tree
 Range Updates, Point Queries 10

Data
Structures II

Range Trees
over Trees
Recall range trees. They were a data structure that for
Range
many types of operations supported range queries and
Updates,
Point Queries
point updates.
Range
Updates,
Range Queries

Range Trees We will now extend this to also support range updates.
of Data
Structures

Solving
Problems in
Subranges
For simplicity, let us tackle the problem of range updates,
Searching a
Range Tree point queries first.
 Problem: Range Updates, Point Queries 11

Data
Structures II

Range Trees
over Trees
Given an array a[n], initially all zeros, support q
Range
Updates, operations, each being one of the following forms:
Point Queries
Update: U l r v. Perform a[l,r) += v.
Range
Updates, Query: Q x. Output a[x].
Range Queries

Range Trees
of Data
Structures

Solving
Problems in
Subranges n, q ≤ 100, 000.
Searching a
Range Tree
 Range Updates, Point Queries 12

Data
Structures II
Again, we can’t just individually update all elements of the
Range Trees array: that would cost O(n) per operation.
over Trees

Range
Updates,
Point Queries
So we are going to do the same as we did for range
Range
queries.
Updates,
Range Queries

Range Trees Suppose our update tells us to perform a[l,r) += x.

of Data
Structures

Solving This is the same as performing a[l,m) += x and

Problems in
Subranges a[m,r) += x.
Searching a
Range Tree
So we can partition our initial update into smaller ranges
however we wish.
 Range Updates, Point Queries 13

Data
Structures II
We will decompose [l, r) into ranges that correspond
Range Trees directly to nodes in our range tree in the same way that
over Trees
we do for range queries.
Range
Updates,
Point Queries

Range
For each node we will store a lazy counter that keeps the
Updates,
Range Queries
sum of all updates to that node’s range of responsibility.
Range Trees
of Data
Structures To query an index, we need to know all updates to ranges
Solving that contain said index.
Problems in
Subranges

Searching a
Range Tree
For a range tree there are O(log n) of these ranges, and
they are exactly the ranges that appear on the path from
the root to the leaf corresponding to that index.
 Range Updates, Point Queries 14

Data
Structures II

Range Trees
Let’s update the range [2, 8) with v = 3.
over Trees

Range
Updates,
Point Queries

Range 0 [0, 8) [2, 8)

Updates,
Range Queries

Range Trees 0 [0, 4) 0 [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 0 [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 0 0 0 0 0 0 0
 Range Updates, Point Queries 15

Data
Structures II

As with range queries, we will push the update range down

Range Trees
over Trees into the applicable nodes.
Range
Updates,
Point Queries

Range
Updates,
0 [0, 8)
Range Queries

Range Trees
of Data 0 [0, 4) 3 [4, 8) [4, 8)
Structures

Solving
Problems in
Subranges
0 [0, 2) 3 [2, 4) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Point Queries 16

Data
Structures II

Now let’s assume we’ve been given a second update, for

Range Trees
over Trees the range [1, 5) with v = 7.
Range
Updates,
Point Queries

Range
Updates,
0 [0, 8) [1, 5)
Range Queries

Range Trees
of Data 0 [0, 4) 3 [4, 8)
Structures

Solving
Problems in
Subranges
0 [0, 2) 3 [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Point Queries 17

Data
Structures II

Range Trees
The range decomposition is [1, 2), [2, 4), [4, 5).
over Trees

Range
Updates,
Point Queries

Range 0 [0, 8)
Updates,
Range Queries

Range Trees 0 [0, 4) 3 [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 3 + 7 [2, 4) [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 7 0 0 7 0 0 0
 Range Updates, Point Queries 18

Data
Structures II

Note that we have not changed the value for the node
Range Trees
over Trees corresponding to the range [4, 8).
Range
Updates,
Point Queries

Range
Updates,
0 [0, 8)
Range Queries

Range Trees
of Data 0 [0, 4) 3 [4, 8)
Structures

Solving
Problems in
Subranges
0 [0, 2) 10 [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 7 0 0 7 0 0 0
 Range Updates, Point Queries 19

Data
Structures II
Let’s try to query what a[4] is.
Range Trees The nodes responsible for a range containing i = 4 are the
over Trees
ones from the leaf for i to the root.
Range
Updates,
Point Queries

Range
0 [0, 8)
Updates,
Range Queries

Range Trees 0 [0, 4) 3 [4, 8)

of Data
Structures

Solving
Problems in
0 [0, 2) 10 [2, 4) [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 7 0 0 7 0 0 0

The sum of these is 0 + 3 + 0 + 7 = 10, hence a[4] = 10.

 Range Updates, Point Queries 20

Data
Structures II const int N = 100100;
long long lazyadd [1 <<18];

Range Trees int n;

over Trees
// The root node is responsible for [0, n). Update range [uL , uR)
Range // Compare to range query code.
Updates, void update(int uL , int uR , int v, int i = 1, int cL = 0, int cR = n) {
Point Queries if (uL == cL && uR == cR) {
lazyadd [i] += v;
Range return;
Updates, }
Range Queries int mid = (cL + cR) / 2;
if (uL < mid) update(uL , min(uR , mid), v, i * 2, cL , mid);
Range Trees
if (uR > mid) update(max(uL , mid), uR , v, i * 2 + 1, mid , cR);
of Data
}
Structures

Solving long long query(int p, int i = 1, int cL = 0, int cR = n) {

Problems in if (cR - cL == 1) {
Subranges return lazyadd [i];
}
Searching a int mid = (cL + cR) / 2;
Range Tree long long ans = lazyadd [i];
if (p < mid) ans += query(p, i * 2, cL , mid);
else ans += query(p, i * 2 + 1, mid , cR);
return ans;
}
 Range Updates, Point Queries 21

Data
Structures II Complexity: Still O(log n) per operation, for the same
reasons as before.
Range Trees
over Trees
Works for most operations that can be broken down into
Range
Updates, smaller ranges.
Point Queries

Range You also need to be able to accumulate the operation so

Updates,
Range Queries that you can store all the information in the lazy counter.
Range Trees So for example, the operation a[i] = a[i] mod vq is an
of Data
Structures issue.
Solving
Problems in However, covers most operations you would naturally
Subranges
think of, e.g: multiply, divide, xor, and, etc …
Searching a
Range Tree
Can also sometimes do multiple different kinds of updates
but this is more finnicky and depends on the specific
updates and probably requires lazy propagation.
 Dynamic Distance on a Tree 22

Data
Structures II
Problem Statement Given a weighted tree, all edges
Range Trees initially 0. Support q operations, each one taking one of
over Trees
the following forms:
Range
Updates, Update U i j w: Add w to the weight of the edge
Point Queries
between i and j.
Range
Updates,
Query Q i j: Output the shortest distance between i and
Range Queries j.
Range Trees
of Data
Structures
Input A tree described as n − 1 edges, followed by q
Solving
Problems in operations. 1 ≤ n, q ≤ 100, 000.
Subranges

Searching a
Range Tree
Output For each query, an integer, the shortest distance
from i to j.
 Dynamic Distance on a Tree 23

Data
Structures II 0

Range Trees
over Trees

Range 1 4
Updates,
Point Queries

Range
Updates,
Range Queries 2 3
Range Trees
of Data
Structures
Sample Input: Sample Output:
Solving
Problems in
Subranges U 0 1 3 3
Searching a Q 4 3 7
Range Tree
U 0 1 -1
U 3 1 5
Q 3 4
 Dynamic Distance on a Tree 24

Data
Structures II

Recall our solution for the static problem.

Range Trees
over Trees

Range
Updates, Let l = lca(i, j). We split the path from i to j into a path
Point Queries
from i to l followed by a path from j to l.
Range
Updates,
Range Queries

Range Trees Let weight_sum(i) be the sum of weights from the root
of Data
Structures to i. The answer is then just
Solving weight_sum(i) + weight_sum(j) - 2*weight_sum(l).
Problems in
Subranges

Searching a
Range Tree Our updates don’t change the tree structure but change
weight_sum. So this is what we need to update.
 Dynamic Distance on a Tree 25

Data
Structures II

Range Trees
over Trees
When we update an edge, what weight sums do we
Range
update?
Updates,
Point Queries

Range
Updates,
Range Queries Every node whose path to the root goes through said
Range Trees edge. In other words, every node in the edge’s subtree.
of Data
Structures

Solving
Problems in
Subranges
So we should maintain weight_sum using a range tree
Searching a
Range Tree and update it using subtree updates.
 Dynamic Distance on a Tree 26

Data
Structures II using namespace std;

const int N = 100100;

Range Trees
// Suppose you already have your tree set up.
over Trees
int depth[N]; // Depth in tree ( ignores weight ).
Range int lca(int a, int b);
Updates,
Point Queries // A node is responsible for the range [ startRange [v], endRange [v])
int indexInRangeTree [N], startRange [N], endRange [N];
Range // A range tree supporting range updates of add , point queries of value .
Updates, long long rangeTree [1<<18];
Range Queries void update(int uL , int uR , long long v); // value [uL ,uR) += v
long long query(int q);
Range Trees
of Data void update_edge (int i, int j, long long v) {
Structures // To update the edge 's subtree , we need to know which of the 2 nodes are
lower .
Solving if (depth[i] > depth[j])
Problems in swap(i, j);
Subranges update( startRange [j], endRange [j], v);
}
Searching a
Range Tree long long get_tree_distance (int i, int j) {
int l = lca(i, j);
return query( indexInRangeTree [i]) + query( indexInRangeTree [j])
- 2* query( indexInRangeTree [l]);
}
 Table of Contents 27

Data
Structures II

Range Trees
1 Range Trees over Trees
over Trees

Range
Updates, 2 Range Updates, Point Queries
Point Queries

Range
Updates, 3 Range Updates, Range Queries
Range Queries

Range Trees
of Data
Structures
4 Range Trees of Data Structures
Solving
Problems in
Subranges
5 Solving Problems in Subranges
Searching a
Range Tree
6 Searching a Range Tree
 Range Updates, Range Queries 28

Data
Structures II

Range Trees
over Trees

Range
Updates,
Point Queries

Range
Updates, Now let’s try range updates and range queries.
Range Queries

Range Trees
of Data
Structures

Solving
Problems in
Subranges

Searching a
Range Tree
 Problem: Range Updates, Range Queries 29

Data
Structures II

Range Trees
over Trees
Given an array a[n], initially all zeros, support q
Range
Updates, operations, each being one of the following forms:
Point Queries
Update: U l r v. Perform
∑r−1a[l,r) += v.
Range
Updates, Query: Q l r. Output i=l a[i].
Range Queries

Range Trees
of Data
Structures

Solving
Problems in
Subranges n, q ≤ 100, 000.
Searching a
Range Tree
 Range Updates, Range Queries 30

Data
Structures II We will support range updates in the same way we did for
point queries. Instead, we will change how we do range
Range Trees queries.
over Trees

Range
In our earlier example, for each node we just stored the
Updates,
Point Queries
lazy counter. This was enough as every query involved
Range
walking from the root to a leaf.
Updates,
Range Queries
However, recall to handle range queries in good time
Range Trees complexity we terminate our recursion once we’ve found a
of Data
Structures
node that matches our current query range.
Solving Hence for each node we will need to store 2 values, the
Problems in
Subranges lazy counter and the sum of the node’s range of
Searching a responsibility.
Range Tree
2 major changes:
1 Maintain for each node its lazy counter and the sum of its
range.
2 Support updates through lazy propagation.
 Lazy Propagation 31

Data
Structures II

Range Trees
Lazy propagation is the idea that whenever we touch a
over Trees node, we should propagate that node’s updates to its
Range
Updates,
children.
Point Queries

Range
Updates,
Range Queries For our example, propagate means add the lazy counter of
Range Trees
of Data
node i to its two children and set the lazycounter of node i
Structures to 0.
Solving
Problems in
Subranges

Searching a Essentially, instead of doing a[l, r)+ = v, we break the

Range Tree
update into a[l, m)+ = v and a[m, r)+ = v.
 Lazy Propagation 32

Data
Structures II

Range Trees
over Trees

Range 0 [0, 8)
Updates,
Point Queries

Range
Updates,
0 [0, 4) 3 [4, 8)
Range Queries

Range Trees
of Data 0 [0, 2) 10 [2, 4) 0 [4, 6) 0 [6, 8)
Structures

Solving
Problems in
Subranges
0 7 0 0 7 0 0 0
Searching a
Range Tree
 Lazy Propagation 33

Data
Structures II

Range Trees
Let’s try querying a[5].
over Trees

Range
Updates,
Point Queries

Range 0 [0, 8)
Updates,
Range Queries

Range Trees 0 [0, 4) 3 [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 10 [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 7 0 0 7 0 0 0
 Lazy Propagation 34

Data
Structures II

Range Trees
Let’s try querying a[5].
over Trees

Range
Updates,
Point Queries

Range 0 [0, 8)
Updates,
Range Queries

Range Trees 0 [0, 4) 3 [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 10 [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 7 0 0 7 0 0 0
 Lazy Propagation 35

Data
Structures II

Range Trees
Let’s try querying a[5].
over Trees

Range
Updates,
Point Queries

Range 0 [0, 8)
Updates,
Range Queries

Range Trees 0 [0, 4) 3 [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 10 [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 7 0 0 7 0 0 0
 Lazy Propagation 36

Data
Structures II

Range Trees
Let’s try querying a[5].
over Trees

Range
Updates,
Point Queries

Range 0 [0, 8)
Updates,
Range Queries

Range Trees 0 [0, 4) 0 [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 10 [2, 4) 3 [4, 6) 3 [6, 8)
Subranges

Searching a
Range Tree 0 7 0 0 7 0 0 0
 Lazy Propagation 37

Data
Structures II

Range Trees
Let’s try querying a[5].
over Trees

Range
Updates,
Point Queries

Range 0 [0, 8)
Updates,
Range Queries

Range Trees 0 [0, 4) 0 [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 10 [2, 4) 3 [4, 6) 3 [6, 8)
Subranges

Searching a
Range Tree 0 7 0 0 7 0 0 0
 Lazy Propagation 38

Data
Structures II

Range Trees
Let’s try querying a[5].
over Trees

Range
Updates,
Point Queries

Range 0 [0, 8)
Updates,
Range Queries

Range Trees 0 [0, 4) 0 [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 10 [2, 4) 0 [4, 6) 3 [6, 8)
Subranges

Searching a
Range Tree 0 7 0 0 10 3 0 0
 Lazy Propagation 39

Data
Structures II
Let’s try querying a[5].
Range Trees
over Trees

Range
Updates, 0 [0, 8)
Point Queries

Range
Updates,
Range Queries
0 [0, 4) 0 [4, 8)
Range Trees
of Data
Structures 0 [0, 2) 10 [2, 4) 0 [4, 6) 3 [6, 8)
Solving
Problems in
Subranges
0 7 0 0 10 3 0 0
Searching a
Range Tree

Hence a[5] = 3.
 Lazy Propagation 40

Data
Structures II

Range Trees
over Trees

Range
This ensures when we read the sum of a range from a
Updates,
Point Queries
node, we won’t be missing any updates that are stored in
Range
the lazy counter of one of the node’s ancestors.
Updates,
Range Queries

Range Trees
of Data
Structures

Solving Complexity Overhead? No overhead, propagation is an

Problems in
Subranges O(1) operation per node.
Searching a
Range Tree
 Storing Counter and Sum 41

Data
Structures II To support range queries, for each node we also need to
store the sum of its range.
Range Trees
over Trees But because of range updates, we can’t literally do this
Range (else we’d need to update every node within the update
Updates,
Point Queries range).
Range
Updates, Our invariant will be: Each node stores what the sum of
Range Queries
its range would be, accounting only for lazy counters
Range Trees
of Data within its subtree.
Structures

Solving All lazy counters above each node are ignored.

Problems in
Subranges This way, an update only needs to modify the nodes
Searching a
Range Tree
encountered in the update’s recursion.
This will suffice since lazy propagation ensures when we
actually query a node all its ancestors will have lazy
counter 0.
 Range Updates, Range Queries 42

Data
Structures II
Sum of a node’s range will always be shown.
Range Trees
over Trees
Nonzero lazy counters will be written in brackets to the
Range right.
Updates,
Point Queries

Range
Updates,
Range Queries
0 [0, 8)
Range Trees
of Data
Structures 0 [0, 4) 0 [4, 8)
Solving
Problems in
Subranges
0 [0, 2) 0 [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree

0 0 0 0 0 0 0 0
 Range Updates, Range Queries 43

Data
Structures II

Range Trees
Let’s update the range [2, 8) with v = 3.
over Trees

Range
Updates,
Point Queries

Range 0 [0, 8) [2, 8)

Updates,
Range Queries

Range Trees 0 [0, 4) 0 [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 0 [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 0 0 0 0 0 0 0
 Range Updates, Range Queries 44

Data
Structures II

This is done recursively, just like queries, so we’ll

Range Trees
over Trees summarise.
Range
Updates,
Point Queries

Range
Updates,
0 [0, 8) [2, 8)
Range Queries

Range Trees
of Data 0 [0, 4) [2, 4) 0 [4, 8) [4, 8)
Structures

Solving
Problems in
Subranges
0 [0, 2) 0 [2, 4) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Range Queries 45

Data
Structures II

Let’s update the left side first.

Range Trees
over Trees We need to update the lazy counter and also the sum.
Range
Updates,
Point Queries

Range
Updates, 0 [0, 8) [2, 8)
Range Queries

Range Trees
of Data 0 [0, 4) [2, 4) 0 [4, 8) [4, 8)
Structures

Solving
Problems in
Subranges 0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Range Queries 46

Data
Structures II
We then return from this branch of the recursion.
Range Trees
over Trees
As we’re returning we will update the nodes we passed
Range through in this branch.
Updates,
Point Queries

Range
Updates,
Range Queries
0 [0, 8) [2, 8)
Range Trees
of Data
Structures 6 [0, 4) 0 [4, 8) [4, 8)
Solving
Problems in
Subranges
0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree

0 0 0 0 0 0 0 0
 Range Updates, Range Queries 47

Data
Structures II

Now our recursion enters the other branch. Same as

Range Trees
over Trees before.
Range
Updates,
Point Queries

Range
Updates,
0 [0, 8) [2, 8)
Range Queries

Range Trees
of Data 6 [0, 4) 12(3) [4, 8)
Structures

Solving
Problems in
Subranges
0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Range Queries 48

Data
Structures II

We now return from the right branch.

Range Trees
over Trees We now update the root node before returning.
Range
Updates,
Point Queries

Range
Updates, 18 [0, 8)
Range Queries

Range Trees
of Data 6 [0, 4) 12(3) [4, 8)
Structures

Solving
Problems in
Subranges 0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Range Queries 49

Data
Structures II

We now return from the right branch.

Range Trees
over Trees We now update the root node before returning.
Range
Updates,
Point Queries

Range
Updates, 18 [0, 8)
Range Queries

Range Trees
of Data 6 [0, 4) 12(3) [4, 8)
Structures

Solving
Problems in
Subranges 0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Range Queries 50

Data
Structures II

Let’s update a second update to the range [0, 8) with

Range Trees
over Trees v = 4.
Range
Updates,
Point Queries

Range
Updates,
18 [0, 8) [0, 8)
Range Queries

Range Trees
of Data 6 [0, 4) 12(3) [4, 8)
Structures

Solving
Problems in
Subranges
0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Range Queries 51

Data
Structures II

Range Trees
Since the root’s range matches we just update the root.
over Trees

Range
Updates,
Point Queries

Range 18 + 4*8(4) [0, 8)

Updates,
Range Queries

Range Trees 6 [0, 4) 12(3) [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 0 0 0 0 0 0 0
 Range Updates, Range Queries 52

Data
Structures II

Range Trees
Note how we did not modify any node but the root.
over Trees

Range
Updates,
Point Queries

Range 50(4) [0, 8)

Updates,
Range Queries

Range Trees 6 [0, 4) 12(3) [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 0 0 0 0 0 0 0
 Range Updates, Range Queries 53

Data
Structures II

Range Trees
Let’s now query the sum of the range [2, 8).
over Trees

Range
Updates,
Point Queries

Range 50(4) [0, 8) [2, 8)

Updates,
Range Queries

Range Trees 6 [0, 4) 12(3) [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 0 0 0 0 0 0 0
 Range Updates, Range Queries 54

Data
Structures II

Whenever we encounter a node, we lazy propagate out its

Range Trees
over Trees lazy counter.
Range
Updates,
Point Queries

Range
Updates,
50(4) [0, 8) [2, 8)
Range Queries

Range Trees
of Data 6(0) [0, 4) 12(3) [4, 8)
Structures

Solving
Problems in
Subranges
0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Range Queries 55

Data
Structures II

When we lazy propagate, we also need to change node

Range Trees
over Trees sums.
Range
Updates,
Point Queries

Range
Updates,
50(0) [0, 8) [2, 8)
Range Queries

Range Trees
of Data 6 + 4*4(4) [0, 4) 12+4*4(7) [4, 8)
Structures

Solving
Problems in
Subranges
0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Range Queries 56

Data
Structures II

When we lazy propagate, we also need to change node

Range Trees
over Trees sums.
Range
Updates,
Point Queries

Range
Updates,
50(0) [0, 8) [2, 8)
Range Queries

Range Trees
of Data 22(4) [0, 4) 28(7) [4, 8)
Structures

Solving
Problems in
Subranges
0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Range Queries 57

Data
Structures II

Range Trees
Now we do the recursion for answering the query.
over Trees

Range
Updates,
Point Queries

Range 50 [0, 8) [2, 8)

Updates,
Range Queries

Range Trees 22(4) [0, 4) [2, 4) 28(7) [4, 8) [4, 8)

of Data
Structures

Solving
Problems in 0 [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 0 0 0 0 0 0 0
 Range Updates, Range Queries 58

Data
Structures II

Range Trees
Again, we need to lazy propagate.
over Trees

Range
Updates,
Point Queries

Range 50 [0, 8) [2, 8)

Updates,
Range Queries

Range Trees 22(4) [0, 4) [2, 4) 28(7) [4, 8) [4, 8)

of Data
Structures

Solving
Problems in 0(0) [0, 2) 6(3) [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 0 0 0 0 0 0 0
 Range Updates, Range Queries 59

Data
Structures II

Range Trees
Again, we need to lazy propagate.
over Trees

Range
Updates,
Point Queries

Range 50 [0, 8) [2, 8)

Updates,
Range Queries

Range Trees 22 [0, 4) [2, 4) 28(7) [4, 8) [4, 8)

of Data
Structures

Solving
Problems in 8(4) [0, 2) 14(7) [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 0 0 0 0 0 0 0
 Range Updates, Range Queries 60

Data
Structures II

Range Trees
Now we recurse again.
over Trees

Range
Updates,
Point Queries

Range 50 [0, 8) [2, 8)

Updates,
Range Queries

Range Trees 22 [0, 4) [2, 4) 28(7) [4, 8) [4, 8)

of Data
Structures

Solving
Problems in 8(4) [0, 2) 14(7) [2, 4) [2, 4) 0 [4, 6) 0 [6, 8)
Subranges

Searching a
Range Tree 0 0 0 0 0 0 0 0
 Range Updates, Range Queries 61

Data
Structures II
For simplicity, we’ll just say we don’t lazy propagate when
Range Trees
we’ve found the right range.
over Trees

Range
Updates,
Point Queries
50 [0, 8) [2, 8)
Range
Updates,
Range Queries 22 [0, 4) [2, 4) 28(7) [4, 8) [4, 8)
Range Trees
of Data
Structures 8(4) [0, 2) 14(7) [2, 4) [2, 4) 0 [4, 6) 0 [6, 8)
Solving
Problems in
Subranges
0 0 0 0 0 0 0 0
Searching a
Range Tree

So we return the result we have obtained up the chain and

continue the query in the other branch.
 Range Updates, Range Queries 62

Data
Structures II
So we return the result we have obtained up the chain and
Range Trees
continue the query in the other branch.
over Trees

Range
Updates,
Point Queries
50 [0, 8) [2, 8)
Range
Updates,
Range Queries 22 [0, 4) [2, 4) 28(7) [4, 8) [4, 8)
Range Trees
of Data
Structures 8(4) [0, 2) 14(7) [2, 4) [2, 4) 0 [4, 6) 0 [6, 8)
Solving
Problems in
Subranges
0 0 0 0 0 0 0 0
Searching a
Range Tree

Note how all ancestors of the node responsible for the

range [2, 4) have lazy counter equal to 0.
 Range Updates, Range Queries 63

Data
Structures II

Now we continue in the second branch where we

Range Trees
over Trees immediately find the node with the right range.
Range
Updates,
Point Queries

Range
Updates,
50 [0, 8) [2, 8) 14 + ?
Range Queries

Range Trees
of Data 22 [0, 4) [2, 4) 28(7) [4, 8) [4, 8)
Structures

Solving
Problems in
Subranges
8(4) [0, 2) 14(7) [2, 4) [2, 4) 0 [4, 6) 0 [6, 8)
Searching a
Range Tree
0 0 0 0 0 0 0 0
 Range Updates, Range Queries 64

Data
Structures II

So we immediately return with the value.

Range Trees
over Trees

Range
Updates, 50 [0, 8) [2, 8) 14 + 28
Point Queries

Range
Updates,
Range Queries 22 [0, 4) [2, 4) 28(7) [4, 8) [4, 8)
Range Trees
of Data
Structures 8(4) [0, 2) 14(7) [2, 4) [2, 4) 0 [4, 6) 0 [6, 8)
Solving
Problems in
Subranges
0 0 0 0 0 0 0 0
Searching a
Range Tree

And we now return from the root with the answer 42.
 Range Updates, Range Queries 65

Data
Structures II
Implementation wise, it helps to introduce some
Range Trees terminology.
over Trees

Range
Updates, In a recursion, call the “preorder procedure” the procedure
Point Queries
we call before recursing.
Range
Updates,
Range Queries
Call the “postorder procedure” the procedure we call after
Range Trees
of Data we’ve returned from all children.
Structures

Solving
Problems in Then we will implement propagation as a preorder
Subranges
procedure.
Searching a
Range Tree

And for updates, recalculating a node’s sum is a postorder

procedure.
 Range Updates, Range Queries 66

Data
Structures II
using namespace std;

const int N = 100100;

Range Trees long long lazyadd [1<<18], sum [1 < <18];
over Trees
// Procedure for recalculating a node 's sum from its lazy and children .
Range
void recalculate (int id , long long l, long long r) {
Updates,
sum[id] = lazyadd [id] * (r - l);
Point Queries
if (r - l != 1) {
Range sum[id] += sum[id * 2];
Updates, sum[id] += sum[id * 2 + 1];
Range Queries }
}
Range Trees
of Data void update_lazy (int id , long long v, long long l, long long r) {
Structures lazyadd [id] += v;
recalculate (id , l, r);
Solving }
Problems in
Subranges // Preorder procedure for propagation . Do NOT call it on leaves .
void propagate (int id , long long l, long long r) {
Searching a long long mid = (l + r) / 2;
Range Tree update_lazy (id * 2, lazyadd [id], l, mid);
update_lazy (id * 2 + 1, lazyadd [id], mid , r);
lazyadd [id] = 0;
}
 Range Updates, Range Queries 67

Data
Structures II
int n;

// The root node is responsible for [0, n). Update range [uL , uR)
Range Trees void update(int uL , int uR , int v, int i = 1, int cL = 0, int cR = n) {
over Trees if (uL == cL && uR == cR) {
update_lazy (i, v, cL , cR);
Range
return;
Updates,
}
Point Queries
propagate (i, cL , cR);
Range int mid = (cL + cR) / 2;
Updates, if (uL < mid) update(uL , min(uR , mid), v, i * 2, cL , mid);
Range Queries if (uR > mid) update(max(uL , mid), uR , v, i * 2 + 1, mid , cR);
recalculate (i, cL , cR);
Range Trees }
of Data
Structures long long query(int qL , int qR , int i = 1, int cL = 0, int cR = n) {
if (qL == cL && qR == cR) {
Solving return sum[i];
Problems in }
Subranges propagate (i, cL , cR);
int mid = (cL + cR) / 2;
Searching a long long ans = 0;
Range Tree if (qL < mid) ans += query(qL , min(qR , mid), i * 2, cL , mid);
if (qR > mid) ans += query(max(qL , mid), qR , i * 2 + 1, mid , cR);
return ans;
}
 Range Updates, Range Queries 68

Data
Structures II
Complexity: O(log n) per update/query still. We still visit
the same nodes; the extra propagation and computation is
Range Trees
over Trees just O(1) overhead per node.
Range
Updates,
Point Queries
It is important to make sure you have invariants in mind
Range when implementing range trees.
Updates,
Range Queries
For example, we had the invariant that sum[i] represents
Range Trees
of Data the sum accounting for all lazy updates in the subtree of i.
Structures
Everything else was dictated by maintaining this invariant.
Solving
Problems in
Subranges You could instead have sum[i] account for all lazy
Searching a
Range Tree
updates in the subtree, excluding the lazy counter at node
i itself.

Doesn’t matter, just stay consistent.

 Example: Setting Ranges 69

Data
Structures II

Range Trees Problem Statement: Given an array of integers a[n],

over Trees
initially all 0, support q operations of the forms:
Range
Updates, Update U l r v. Set a[l, r) = v, v ≥ 0.
Point Queries Query Q l r. What is the max of a[l, r)?
Range
Updates,
Range Queries

Range Trees
of Data Input Format: First line, 2 integers, n, q. The following q
Structures
lines each describe an operation.
Solving
Problems in
Subranges

Searching a
Range Tree Constraints: 1 ≤ n, q ≤ 100, 000.
 Example: Setting Ranges 70

Data
Structures II

Range Trees
over Trees Sample Input: Sample Output:
Range
Updates,
Point Queries 5 7 5
Range U 1 3 5 1
Updates,
Range Queries U 2 4 1 3
Range Trees Q 1 3 5
of Data
Structures Q 2 3
Solving U 3 4 3
Problems in
Subranges Q 2 4
Searching a Q 1 5
Range Tree
 Example: Setting Ranges 71

Data
Structures II

We will use the same lazy propagation framework.

Range Trees
over Trees

Range What our nodes store is dictated by the queries.

Updates,
Point Queries

Range
Updates, Each of our nodes needs to store the max for their range
Range Queries
of responsibility, ignoring all lazy values outside that
Range Trees
of Data node’s subtree.
Structures

Solving
Problems in
Subranges
Our lazy values are dictated by the updates.
Searching a
Range Tree
Each of our nodes needs to store the last update applied
to the node.
 Example: Setting Ranges 72

Data
Structures II

Question? For a given node in the range tree how do we

Range Trees
over Trees
know which update most recently covered the node’s
Range range?
Updates,
Point Queries

Range
Updates,
Key Observation: If we lazy propagate, it is the lazy
Range Queries
value of the highest ancestor with a lazy value set.
Range Trees
of Data
Structures

Solving
Why? Because whenever we apply an update, we lazy
Problems in
Subranges
propagate existing updates on the path to the node we’re
Searching a
updating. So no ancestors of the node have lazy values
Range Tree
set. Hence the highest set lazy value is the most recent
update.
 Example: Setting Ranges 73

Data
Structures II

Now we know what we need.

Range Trees
over Trees

Range
Updates,
Our lazy values store the most recent update to a range.
Point Queries These will be lazy propagated. When we lazy propagate
Range
Updates,
we just overwrite our children since we know our update is
Range Queries more recent than our children’s.
Range Trees
of Data
Structures
Each node stores the max of its range, based on only lazy
Solving
Problems in values within its subtree.
Subranges

Searching a
Range Tree
maxrt[i] = lazy[i] if lazy[i] is set, else it is the max
of i’s children.
 Example: Setting Ranges 74

Data
Structures II
using namespace std;

Range Trees const int N = 100100;

over Trees const int UNSET = -1;
// Since A is 0 initially , the default values are correct .
Range int lazyset [1 <<18]; // UNSET if no lazy is set
Updates, int maxrt [1< <18];
Point Queries
// Recalculates a node 's values assuming its children are correct .
Range
// do NOT call these on leaves .
Updates,
void recalculate (int i) {
Range Queries
if ( lazyset [i] != UNSET)
Range Trees maxrt[i] = lazyset [i];
of Data else
Structures maxrt[i] = max(maxrt[i*2], maxrt[i*2+1]);
}
Solving
Problems in void propagate (int i) {
Subranges if ( lazyset [i] == UNSET)
return;
Searching a lazyset [i*2] = lazyset [i*2+1] = lazyset [i];
Range Tree maxrt[i*2] = maxrt[i*2+1] = lazyset [i];
lazyset [i] = UNSET;
}
 Example: Setting Ranges 75

Data
Structures II
int n;

Range Trees void update(int uL , int uR , int v, int i = 1, int cL = 0, int cR = n) {

over Trees if (uL == cL && uR == cR) {
lazyset [i] = maxrt[i] = v;
Range return;
Updates, }
Point Queries propagate (i);
int mid = (cL + cR) / 2;
Range if (uL < mid) update(uL , min(uR , mid), v, i*2, cL , mid);
Updates, if (uR > mid) update(max(uL , mid), uR , v, i*2+1, mid , cR);
Range Queries recalculate (i);
}
Range Trees
of Data int query(int qL , int qR , int i = 1, int cL = 0, int cR = n) {
Structures if (qL == cL && qR == cR) {
return maxrt[i];
Solving
}
Problems in
propagate (i);
Subranges
int mid = (cL + cR) / 2;
Searching a int ans = -1; // note all values are >= 0 in the question .
Range Tree if (qL < mid) ans = max(ans , query(qL , min(qR , mid), i*2, cL , mid));
if (qR > mid) ans = max(ans , query(max(qL , mid), qR , i*2+1, mid , cR));
return ans;
}
 Table of Contents 76

Data
Structures II

Range Trees
1 Range Trees over Trees
over Trees

Range
Updates, 2 Range Updates, Point Queries
Point Queries

Range
Updates, 3 Range Updates, Range Queries
Range Queries

Range Trees
of Data
Structures
4 Range Trees of Data Structures
Solving
Problems in
Subranges
5 Solving Problems in Subranges
Searching a
Range Tree
6 Searching a Range Tree
 Range Tree of Data Structures 77

Data
Structures II

So far we’ve just used range trees to support operations an

Range Trees
over Trees array of integers.
Range
Updates,
Point Queries
But the real power of range trees is in the way it
Range
Updates, decomposes ranges.
Range Queries

Range Trees
of Data
Structures
The nodes can store anything.
Solving
Problems in
Subranges For example other data structures (!!)
Searching a
Range Tree

The most useful is probably a set or other SBBST.

 Problem: Should I bring an Umbrella? 78

Data
Structures II
Problem Statement It’s 2200 and climatology is now the
Range Trees
most hectic job on earth. There is a constant deluge of
over Trees rain predictions concerning the towns in LineLand. There
Range
Updates,
are n towns in LineLand, in a line. Each prediction is of
Point Queries the form U l r d saying that there will be rain in towns
Range
Updates,
[l, r) on day d. Interspersed among these updates, there
Range Queries will be queries of the form Q a d, asking if there is a
Range Trees
of Data
predicted shower in town a on day d.
Structures

Solving Input First line, n, q, the number of towns and operations.

Problems in
Subranges 1 ≤ n, q ≤ 100, 000. Towns are 0 indexed. The next q
Searching a lines are the operations in the specified format.
Range Tree

Output For each operation, 1 if there is forecasted rain

and 0 otherwise.
 Problem: Should I bring an Umbrella? 79

Data
Structures II

Range Trees
over Trees
Sample Input: Sample Output:
Range
Updates,
Point Queries 10 6 1
Range
Updates,
U 0 3 1 0
Range Queries
Q 1 1 0
Range Trees
of Data Q 1 2 1
Structures
Q 3 1
Solving
Problems in U 1 4 1
Subranges
Q 3 1
Searching a
Range Tree
 Problem: Should I bring an Umbrella? 80

Data
Structures II
We have the characteristic range updates that suggest
Range Trees
range tree.
over Trees

Range But it no longer suffices to store a single integer for each

Updates,
Point Queries range.
Range
Updates,
Range Queries To store our predictions we should use a set.
Range Trees
of Data
Structures
We will decompose the range of each prediction using the
Solving range tree and update the sets of each of the
Problems in
Subranges
corresponding nodes.
Searching a
Range Tree To answer a query, we need the predictions corresponding
to each range containing the queried city. This is just the
nodes on the path from the leaf to the root.
 Problem: Should I bring an Umbrella? 81

Data
Structures II #include <set >
using namespace std;

const int N = 100100;

Range Trees
set <int > rt [1 <<18];
over Trees
int n;
Range
Updates, // The root node is responsible for [0, MAX_N ). Update range [uL , uR)
Point Queries void update(int uL , int uR , int v, int i = 1, int cL = 0, int cR = n) {
if (uL == cL && uR == cR) {
Range rt[i]. insert(v);
Updates, return;
Range Queries }
int mid = (cL + cR) / 2;
Range Trees if (uL < mid) update(uL , min(uR , mid), v, i * 2, cL , mid);
of Data if (uR > mid) update(max(uL , mid), uR , v, i * 2 + 1, mid , cR);
Structures }

Solving // Does it rain in index qP on day qD?

Problems in bool query(int qP , int qD , int i = 1, int cL = 0, int cR = n) {
Subranges if (rt[i]. find(qD) != rt[i]. end ())
return true;
Searching a if (cR - cL == 1)
Range Tree return false;
int mid = (cL + cR) / 2;
if (qP < mid) return query(qP , qD , i * 2, cL , mid);
else return query(qP , qD , i * 2 + 1, mid , cR);
}
 Problem: Should I bring an Umbrella? 82

Data
Structures II
Complexity? O(n + q log2 n). Each update and query
Range Trees accesses O(log n) nodes (this is a characteristic of the
over Trees
range decomposition itself) but each access costs O(log n)
Range
Updates, due to the sets.
Point Queries

Range
Updates, Warning: We can’t lazy propagate in this example. This
Range Queries
is because the size of the data we are storing at each node
Range Trees
of Data isn’t constant any more. So the cost of lazy propagation
Structures
per operation is potentially O(n log n) and this does not
Solving
Problems in amortize.
Subranges

Searching a
Range Tree E.g: have 50000 updates to the entire range, then have
the next 50000 be queries forcing a O(n log n) set copy
each time.
 Problem: Should I bring an Umbrella? 83

Data
Structures II
We can actually do much more.
Range Trees
over Trees
We can support other things sets and maps and OSTs
Range
Updates, support, like deleting predictions and finding the closest
Point Queries
rain day or counting the number of cities raining on a
Range
Updates, given day in a range.
Range Queries

Range Trees
of Data If the bounds were different (fewer cities) we could even
Structures
support updates affecting ranges of days, by storing a
Solving
Problems in range tree of days in each node of the original range tree.
Subranges

Searching a
Range Tree Moral: If you need to store different kinds of data while
supporting range operations, consider a range tree of a
suitable data structure.
 Problem: Mapping Neptune 84

Data
Structures II

Range Trees
over Trees

Range
Updates,
Point Queries

Range
Updates,
Another classic problem, finding total area covered by a
Range Queries set of rectangles.
Range Trees
of Data
Structures

Solving
Problems in
Subranges

Searching a
Range Tree
 Problem: Mapping Neptune 85

Data
Structures II
Problem Statement: It’s 2201 and you’re done with
Earth and its unpredictable rainfall. You’ve decided to
Range Trees move to Neptune. After landing, you find out, to your
over Trees
dismay, that not only does it rain on Neptune but it rains
Range
Updates, diamonds. But it’s too late now to turn back so you’ll just
Point Queries
have to make do.
Range
Updates, As we all know, Neptune is a n × n grid with bottom left
Range Queries
corner (0, 0). There are m diamond showers on Neptune,
Range Trees
of Data each a rectangle. You now wish to find how much of
Structures

Solving
Neptune is covered by diamond showers.
Problems in Input: First line 2 integers, n, m. 1 ≤ n, m ≤ 100, 000.
Subranges

Searching a
The next m lines are each of the form x0 y0 x1 y1,
Range Tree describing a diamond shower with bottom left corner
(x0 , y0 ) and upper right corner (x1 , y1 ).
Output: A single integer, the total area of Neptune
covered by the union of all the showers.
 Problem: Mapping Neptune 86

Data
Structures II Sample Input: Sample Output:

Range Trees 4 2 4
over Trees
0 1 2 2
Range
Updates, 1 0 2 3
Point Queries
Explanation:
Range
Updates,
Range Queries

Range Trees
of Data
Structures

Solving
Problems in
Subranges

Searching a
Range Tree
 Problem: Mapping Neptune 87

Data
Structures II
2 common approaches for 2D problems. Either a 2D data
structure or a linear sweep in the y direction while
Range Trees
over Trees maintaining a data structure over x.
Range
Updates, Latter is generally faster and easier.
Point Queries

Range
Updates,
For each row, what do we need to track?
Range Queries

Range Trees Which columns currently have a rectangle.

of Data
Structures
Standard way of doing this is create 2 events per rectangle,
Solving
Problems in one at y0 instructing us to activate the rectangle, one at
Subranges
y1 instructing us to deactivate the rectangle.
Searching a
Range Tree
Suppose we have done this so we know which rectangles
are active. How do we track how many columns have a
rectangle?
 Problem: Mapping Neptune 88

Data
Structures II
An active rectangle covers a range of x coordinates so
Range Trees …range tree!
over Trees

Range
Updates,
Point Queries
The query we need to support is count the number of
Range
indices that are covered.
Updates,
Range Queries

Range Trees
We need to support the updates:
of Data
Structures
1 Add a range.
Solving
2 Remove a range.
Problems in
Subranges

Searching a So we have a range update, range query situation.

Range Tree

What do our nodes store and what are the lazy counters?
 Problem: Mapping Neptune 89

Data
Structures II
What our nodes store is dictated by the queries.
Range Trees
over Trees
Each of our nodes needs to store the number of covered
Range indices in its range.
Updates,
Point Queries
Our lazy counters are dictated by the updates.
Range
Updates,
Range Queries
Each of our nodes needs to store whether a range fully
Range Trees
of Data covers that node’s range.
Structures

Solving We can use a set for the lazy counter. Or we can use a
Problems in
Subranges counter.
Searching a
Range Tree
Warning: We can’t lazy propagate here. Else deleting a
range becomes a nuisance (this becomes more natural if
one thinks of the lazy counter as a set)
 Problem: Mapping Neptune 90

Data
Structures II
So we decompose each update range same as how we
Range Trees always do.
over Trees

Range
Updates,
Point Queries
After decomposing the range, we update the lazy counter
Range at the corresponding nodes.
Updates,
Range Queries

Range Trees In addition, each node stores freq[i], the number of

of Data
Structures covered indices in its range of responsibility only
Solving accounting for lazy counters in its subtree.
Problems in
Subranges

Searching a
Range Tree
Then freq[i] = endRange[i] - startRange[i] if
lazy[i] > 0, otherwise, freq[i] is the sum of its two
children.
 Problem: Mapping Neptune 91

Data #include <iostream >

Structures II #include <vector >
using namespace std;

const int N = 100100;

Range Trees
// Range tree
over Trees
int lazycount [1<<18], freq [1 < <18];
Range int n, m;
Updates,
Point Queries void recompute (int i, int left , int right) {
if ( lazycount [i] > 0) freq[i] = right -left; // range directly covered
Range else if (right -left == 1) freq[i] = 0; // leaf
Updates, else freq[i] = freq[i*2] + freq[i*2+1]; // sum of children
Range Queries }

Range Trees // Update count of [uL , uR) by v

of Data void update(int uL , int uR , int v, int i = 1, int cL = 0, int cR = n) {
Structures if (uL == cL && uR == cR) {
lazycount [i] += v;
Solving recompute (i, cL , cR);
Problems in return;
Subranges }
int mid = (cL + cR) / 2;
Searching a
if (uL < mid) update(uL , min(uR , mid), v, i*2, cL , mid);
Range Tree
if (uR > mid) update(max(uL , mid), uR , v, i*2+1, mid , cR);
recompute (i, cL , cR);
}

int query_total () {
return freq [1];
}
 Problem: Mapping Neptune 92

Data
Structures II struct Event {
int l, r, v;
Event(int _l , int _r , int _v) : l(_l), r(_r), v(_v) {}
Range Trees };
over Trees
// Convention : process events for a y before calculating that value of y.
Range // When calculating yi , we will count covered squares in [yi , yi +1]
Updates, vector <Event > events[N];
Point Queries
int main () {
Range cin >> n >> m;
Updates, for (int i = 0; i < m; i++) {
Range Queries int x0 , y0 , x1 , y1;
cin >> x0 >> y0 >> x1 >> y1;
Range Trees
events[y0]. emplace_back (x0 , x1 , 1);
of Data
events[y1]. emplace_back (x0 , x1 , -1);
Structures
}
Solving
Problems in long long ans = 0;
Subranges for (int i = 0; i < n; i++) {
for (const auto &e: events[i])
Searching a update(e.l, e.r, e.v);
Range Tree ans += query_total ();
}

cout << ans << '\n';

}
 Table of Contents 93

Data
Structures II

Range Trees
1 Range Trees over Trees
over Trees

Range
Updates, 2 Range Updates, Point Queries
Point Queries

Range
Updates, 3 Range Updates, Range Queries
Range Queries

Range Trees
of Data
Structures
4 Range Trees of Data Structures
Solving
Problems in
Subranges
5 Solving Problems in Subranges
Searching a
Range Tree
6 Searching a Range Tree
 Solving Problems in Subranges 94

Data
Structures II

Range Trees
over Trees
We can go further.
Range
Updates,
Point Queries

Range By picking the right state to store we can solve many

Updates,
Range Queries classic linear sweep problems except restricted to a
Range Trees subrange.
of Data
Structures

Solving
Problems in
Subranges
Creating a range tree is kind of like applying divide and
Searching a
Range Tree conquer in this view.
 Solving Problems in Subranges 95

Data
Structures II

Range Trees Each node in our subtree stores the answer for queries
over Trees
that are exactly the node’s range of responsibility [l, r).
Range
Updates,
Point Queries

Range
Updates,
Range Queries
As in divide and conquer, answers contained entirely
Range Trees
within the left half [l, m) or right half [m, r) of the range
of Data
Structures
are handled by the left and right child.
Solving
Problems in
Subranges

Searching a So the crucial (and difficult) part is accounting for possible

Range Tree
solutions that cross m.
 Solving Problems in Subranges 96

Data
Structures II
For this, we will probably need to store additional
Range Trees
metadata.
over Trees

Range Comes down to thinking about what a best solution

Updates,
Point Queries crossing m must look like.
Range
Updates, A subarray crossing the midpoint will be composed of:
Range Queries
a suffix of the left half, and
Range Trees
of Data a prefix of the right half.
Structures

Solving
Problems in But remember, any metadata we add must itself be
Subranges updated in our range tree.
Searching a
Range Tree
Generally this is easier because the metadata is more
specific.
May need to keep adding more metadata until this
stabilises.
 Solving Problems in Subranges 97

Data
Structures II

Suppose we now know how to recalculate a node from its

Range Trees
over Trees two children.
Range
Updates,
Point Queries

Range Then answering a query should be easy.

Updates,
Range Queries

Range Trees
of Data First break our query into subranges based on our range
Structures
tree, as usual.
Solving
Problems in
Subranges

Searching a
Range Tree
Then use our recalculate procedure to merge these
O(log n) ranges.
 Example: Maximum Sum Subrange 98

Data
Structures II

Problem Statement: Given an array of integers a[n],

Range Trees
over Trees initially all 0, support q operations of the forms:
Range Update U i v. Set a[i] = v.
Updates,
Point Queries Query Q i j. Consider the sum of every (contiguous)
Range
subarray of a[i, j). What’s the maximum of these? Treat
Updates, the empty subarray as having sum 0.
Range Queries

Range Trees
of Data
Structures
Input Format: First line, 2 integers, n, q. The following q
Solving
Problems in lines each describe an operation.
Subranges

Searching a
Range Tree
Constraints: 1 ≤ n, q ≤ 100, 000.
 Example: Maximum Sum Subrange 99

Data
Structures II

Range Trees
over Trees Sample Input: Sample Output:
Range
Updates,
Point Queries 5 7 0
Range U 0 -2 3
Updates,
Range Queries U 2 -2 4
Range Trees U 1 3
of Data
Structures Q 0 1
Solving Q 0 5
Problems in
Subranges U 3 3
Searching a Q 0 4
Range Tree
 Example: Maximum Sum Subrange 100

Data
Structures II
Our end goal is a range tree where each node stores the
Range Trees
best answer for its range of responsibility.
over Trees

Range The difficult part is merging two nodes.

Updates,
Point Queries

Range Let’s say we have a node responsible for the range [l, r)
Updates,
Range Queries with children responsible for the ranges [l, m) and [m, r).
Range Trees
of Data
Structures
If the best subarray is solely in [l, m) or solely in [m, r)
Solving
then we are done. What can we say about subarrays
Problems in
Subranges
crossing m?
Searching a
Range Tree Observation: They should start at st such that [st, m)
has maximum possible sum. They should similarly end at
an en such that [m, en) has maximum possible sum.
 Example: Maximum Sum Subrange 101

Data
Structures II
So for each node we should store the maximum possible
sum of a subarray of the form [l, x) and of the form [x, r).
Range Trees
over Trees

Range
Call this bestStart[i] and bestEnd[i].
Updates,
Point Queries
But now we have the same problem. How do we update
Range
Updates, bestStart[i] and bestEnd[i] from the 2 children of i?
Range Queries

Range Trees Again, we follow the same approach.

of Data
Structures

Solving
If bestStart[i] is from a subarray contained entirely in
Problems in
Subranges
the left child then we are done.
Searching a
Range Tree
Otherwise, what can it look like?

Observation: It is of the form [l, m) ∪ [m, x) where x

corresponds to bestStart[rightChild].
 Example: Maximum Sum Subrange 102

Data
Structures II

So
Range Trees
over Trees bestStart[i] = max(bestStart[leftChild],
Range
Updates,
sum[leftChild] + bestStart[rightChild])
Point Queries
where sum[i] is the sum of i’s entire range.
Range
Updates,
Range Queries

Range Trees
of Data
So we now need to maintain sum[i].
Structures

Solving
Problems in
Subranges
But this is easy, you’ve seen this many times.
Searching a
Range Tree

Phew! We’re done now. Only needed to go 3 levels deep!

 Example: Maximum Sum Subrange 103

Data
Structures II

using namespace std;

Range Trees
over Trees const int MAXN = 100100;

Range struct state {

Updates, long long bestStart , bestEnd , sum , bestSubarray ;
Point Queries };

Range // Default value of state is all 0. This is correct for us.

Updates, state rt [1<<18];
Range Queries
state mergeStates (const state& left , const state& right) {
Range Trees
state ret;
of Data
ret. bestStart = max(left.bestStart , left.sum + right. bestStart );
Structures
ret. bestEnd = max(right.bestEnd , left. bestEnd + right.sum);
Solving ret.sum = left.sum + right.sum;
Problems in ret. bestSubarray = max(max(left.bestSubarray , right. bestSubarray ),
Subranges left. bestEnd + right. bestStart );
/* in C++11 , can instead do ret. bestSubarray = max ({ left. bestSubarray ,
Searching a right . bestSubarray , left. bestEnd + right . bestStart }) */
Range Tree return ret;
}
 Example: Maximum Sum Subrange 104

Data
Structures II
int n;

Range Trees void update(int p, int v, int i=1, int cL = 0, int cR = n) {

over Trees if (cR - cL == 1) {
rt[i]. sum = v;
Range rt[i]. bestStart = rt[i]. bestEnd = rt[i]. bestSubarray = max(v ,0);
Updates, return;
Point Queries }
int mid = (cL + cR) / 2;
Range if (p < mid) update(p, v, i * 2, cL , mid);
Updates, else update(p, v, i * 2 + 1, mid , cR);
Range Queries rt[i] = mergeStates (rt[i*2], rt[i*2+1]);
}
Range Trees
of Data state query(int qL , int qR , int i = 1, int cL = 0, int cR = n) {
Structures if (qL == cL && qR == cR) {
return rt[i];
Solving
}
Problems in
int mid = (cL + cR) / 2;
Subranges
if (qR <= mid) return query(qL , qR , i * 2, cL , mid);
Searching a if (qL >= mid) return query(qL , qR , i * 2 + 1, mid , cR);
Range Tree return mergeStates (
query(qL , min(qR , mid), i * 2, cL , mid),
query(max(qL , mid), qR , i * 2 + 1, mid , cR));
}
 Example: Maximum Sum Subrange 105

Data
Structures II

Range Trees
over Trees
Complexity? Still O(log n) for everything, mergeStates
Range
Updates, is an O(1) operation.
Point Queries

Range
Updates,
Range Queries

Range Trees
of Data Moral: While the solution seems involved, the general
Structures
strategy is very simple. Repeatedly consider what is
Solving
Problems in needed to merge 2 different states and see what additional
Subranges
metadata is necessary. Then hope this stabilizes.
Searching a
Range Tree
 Solving Problems in Subranges 106

Data
Structures II

Range Trees
over Trees
We can apply this technique for many simple problems on
Range
a line.
Updates,
Point Queries

Range
Updates,
Range Queries We can also apply this to some DP problems that have
Range Trees
of Data
small state space at any point.
Structures

Solving
Problems in
Subranges
For these, your nodes store matrices detailing how to
Searching a
Range Tree transition between states.
 Table of Contents 107

Data
Structures II

Range Trees
1 Range Trees over Trees
over Trees

Range
Updates, 2 Range Updates, Point Queries
Point Queries

Range
Updates, 3 Range Updates, Range Queries
Range Queries

Range Trees
of Data
Structures
4 Range Trees of Data Structures
Solving
Problems in
Subranges
5 Solving Problems in Subranges
Searching a
Range Tree
6 Searching a Range Tree
 Searching a Range Tree 108

Data
Structures II

For most data structures it suffices to treat them as a

Range Trees
over Trees black box.
Range
Updates,
Point Queries
Hopefully by now you’ve gotten the sense that this is less
Range
Updates, true for range trees.
Range Queries

Range Trees
of Data
Structures Sometimes it is useful to also modify how we traverse a
Solving range tree.
Problems in
Subranges

Searching a
Range Tree This is mainly useful when we are searching for the
first/any value that satisfies some given constraint.
 Searching a Range Tree 109

Data
Structures II Let’s say we want to find any value that satisfies a
criterion X.
Range Trees
over Trees For concreteness, let’s say we want to find any value that’s
Range at least L.
Updates,
Point Queries
In each node, we store enough data to determine if there
Range
Updates, is a value in its range that satisfies X.
Range Queries

Range Trees
For our example, we can store the max of all values in
of Data
Structures
each range.
Solving Once we have this, finding a value is easy. We know for
Problems in
Subranges both children whether there is a value inside their range
Searching a that satisfies X. We then just recurse into whichever side
Range Tree
has a value that satisfies X.
To find the leftmost/rightmost such value, we just bias
our search towards the left or right child.
 Searching a Range Tree 110

Data
Structures II
Suppose now we want to find if any value in a given range
Range Trees [l, r) that satisfies criterion X.
over Trees

Range
Updates, Now we just decompose [l, r) into O(log n) ranges as we
Point Queries
usually do with a range tree.
Range
Updates,
Range Queries
We can then just repeat this for each of the nodes in our
Range Trees
of Data decomposition.
Structures

Solving
Problems in Complexity? O(log n) if you implement correctly since we
Subranges
actually only need to do this once, to the first node which
Searching a
Range Tree we know contains a value satisfying X.

Again, easy to find leftmost/rightmost.

 Problem: First Big Value 111

Data
Structures II

Range Trees
Problem Statement: Given an array, a[n], all initially 0.
over Trees Support q operations of the forms:
Range Update U i v. Set a[i] = v.
Updates,
Point Queries Query Q l r v. What’s the minimum index i ∈ [l, r) such
Range that a[i] > v, or −1 if no such index exists.
Updates,
Range Queries

Range Trees
of Data
Structures Input Format: First line, n, q. Next q lines describe the
Solving operations.
Problems in
Subranges

Searching a
Range Tree
Constraints: 1 ≤ n, q ≤ 100, 000.
 Problem: First Big Value 112

Data
Structures II

Range Trees
over Trees Sample Input: Sample Output:
Range
Updates,
Point Queries 4 7 1
Range U 0 2 -1
Updates,
Range Queries U 1 3 0
Range Trees Q 0 4 2 0
of Data
Structures Q 0 4 3
Solving Q 0 4 1
Problems in
Subranges U 0 4
Searching a Q 0 4 2
Range Tree
 Problem: First Big Value 113

Data
Structures II
To guide our search we need to know whether a range
Range Trees contains a value that is at least v.
over Trees

Range
Updates, For this, it suffices to store the max of each range.
Point Queries

Range
Updates, We know how to maintain this, it’s just a point update,
Range Queries
range query range tree.
Range Trees
of Data
Structures
Now to find a value that is at least v we just need to
Solving
Problems in search only nodes with max[i] > v and terminate our
Subranges
search once we have found a value.
Searching a
Range Tree

To find the first such i, just always search the left child’s
subtree first.
 Problem: First Big Value 114

Data
Structures II
Implementation Details:
Range Trees
over Trees So far we’ve only recursed into nodes we need to by
Range
Updates,
checking before recursing. For this it is a bit easier to
Point Queries
always recurse and return immediately if we’ve recursed
Range
Updates, into a node whose range is disjoint from the query range.
Range Queries

Range Trees
of Data To find an index we have to recurse down to the leaves.
Structures
So we no longer early exit when the query range is the
Solving
Problems in same as the node’s range.
Subranges

Searching a
Range Tree Instead we early terminate once we have found a leaf. To
support this, our recursion will return a boolean indicating
if we have found an index.
 Problem: First Big Value 115

Data
Structures II

Range Trees
over Trees using namespace std;

Range const int N = 100100;

Updates, int maxrt [1< <18];
Point Queries int n;

Range // Standard max range tree.

Updates, void update(int p, int v, int i = 1, int cL = 0, int cR = n) {
Range Queries if (cR - cL == 1) {
maxrt[i] = v;
Range Trees
return;
of Data
}
Structures
int mid = (cL + cR) / 2;
Solving if (p < mid) update(p, v, i*2, cL , mid);
Problems in else update(p, v, i*2+1, mid , cR);
Subranges maxrt[i] = max(maxrt[i*2], maxrt[i*2+1]);
}
Searching a
Range Tree
 Problem: First Big Value 116

Data
Structures II

bool query_rec (int qL , int qR , int v, int &foundPlc , int i = 1, int cL = 0, int
Range Trees cR = n) {
over Trees // Query range does not intersect the node 's range .
if (qL >= cR || qR <= cL) return false;
Range
// Nothing in i's range is big enough
Updates,
if (maxrt[i] <= v) return false;
Point Queries
if (cR - cL == 1) {
Range foundPlc = cL;
Updates, return true;
Range Queries }
int mid = (cL + cR) / 2;
Range Trees if ( query_rec (qL , qR , v, foundPlc , i*2, cL , mid)) return true;
of Data if ( query_rec (qL , qR , v, foundPlc , i*2+1, mid , cR)) return true;
Structures return false;
}
Solving
Problems in int query(int qL , int qR , int v) {
Subranges int ans = -1;
query_rec (qL , qR , v, ans);
Searching a return ans;
Range Tree }
 Problem: First Big Value 117

Data
Structures II
Complexity? Actually still O(log n) per operation.
Range Trees
over Trees

Range
Recall our previous recursions stopped whenever we
Updates,
Point Queries
encountered a node whose range was entirely contained in
Range
[qL, qR).
Updates,
Range Queries

Range Trees In this recursion, whenever we encounter such a node,

of Data
Structures either its max value is too low and we stop anyways, or
Solving the node contains the index we are looking for.
Problems in
Subranges

Searching a
Range Tree
The latter case only occurs once and the search for the
index is O(log n) since we only recurse from a node if we
know for sure its range contains the desired index.
 Searching a Range Tree 118

Data
Structures II

Range Trees
over Trees

Range
Updates,
Point Queries

Range
Updates,
This trick is useful for finding if an event has occurred in
Range Queries the array.
Range Trees
of Data
Structures

Solving
Problems in
Subranges

Searching a
Range Tree
 Problem: Rising Water 119

Data
Structures II
Problem Statement:
It is 2155 and Earth has been renamed Water. LineLand
Range Trees
over Trees with its constant showers has been particularly devastated.
Range LineLand consists of n towns in a row, each with a height
Updates,
Point Queries hi . Initially all of these have water level 0.
Range
Updates,
The climatologists of LineLand forecast there will be m
Range Queries showers, the i-th raising the water levels of towns [li , ri ) by
Range Trees
of Data
wi .
Structures The mayor of LineLand wants to know how many towns
Solving
Problems in
are underwater (total water level is greater than the height
Subranges of the town) after each shower.
Searching a
Range Tree
Input Format: First line, 2 integers, n, m.
1 ≤ n, m ≤ 500, 000. Next line, n integers, the initial
heights of the towns. Next m lines each describe a shower.
 Problem: Rising Water 120

Data
Structures II

Range Trees
over Trees

Range
Updates,
Point Queries Sample Input: Sample Output:
Range
Updates, 3 2 1
Range Queries
1 4 2 2
Range Trees
of Data 0 2 3
Structures

Solving
1 3 2
Problems in
Subranges

Searching a
Range Tree
 Problem: Rising Water 121

Data
Structures II

Observation 1: Once a town is underwater, it is always

Range Trees
over Trees underwater.
Range
Updates,
Point Queries
So we just need to find out what towns change from
Range
Updates, above water to underwater after each operation.
Range Queries

Range Trees
of Data
Structures
What is the criterion for a town to be underwater?
Solving
Problems in
Subranges That total_water[i] > height[i].
Searching a
Range Tree

Alternatively that 0 > height[i] - total_water[i].

 Problem: Rising Water 122

Data
Structures II

Range Trees
over Trees
So to know if there is a new town underwater, we just
Range
need to know if mini (height[i] − total_water[i]) < 0.
Updates,
Point Queries

Range
Updates,
Range Queries We can then delete this town so we do not count it more
Range Trees than once then repeat.
of Data
Structures

Solving
Problems in
Subranges
For this problem, setting a town’s height to infinity is as
Searching a
Range Tree good as deleting the town.
 Problem: Rising Water 123

Data #include <iostream >

Structures II using namespace std;

const int N = 500500;

const int INF = 1000*1000*1000+7; // large height to never go underwater
Range Trees
int minrt [1< <20]; // standard range update min range tree
over Trees
int n, m;
Range
Updates, void update(int uL , int uR , int v); // standard function for a[uL , uR) += v
Point Queries int query(int qL , int qR , int v); // returns index of any value < 0, or -1 if
none exist
Range
Updates, int main () {
Range Queries cin >> n >> m;
for (int i = 0; i < n; i++) {
Range Trees int cH;
of Data cin >> cH;
Structures update(i, i+1, cH);
}
Solving
Problems in int ans = 0;
Subranges for (int i = 0; i < m; i++) {
int a, b, w, cInd;
Searching a
cin >> a >> b >> w;
Range Tree
update(a, b, -w);
while (( cInd = query (0, n, 0)) != -1) {
ans ++;
update(cInd , cInd +1, INF); // " delete " cInd
}
cout << ans << '\n';
}