Arrays and searching 0/121

Segment trees for range queries and updates · 2 of 3 Advanced

Custom combine rules

Decide what a node stores and how two children combine, walk down the tree to find a position, and keep several values per node.

2,268 words · 11 min read

Part 1 of 5 Combine rules

Combine rules and their identities

Turning the tree of minimums into a tree of sums changed two things: how two children are combined, and what a node outside the query returns. Other answers come from making those two choices differently. Here they are for five answers, with aa and bb standing for the values of the two children:

Five answers a segment tree can store
Answer for a rangeCombine two childrenA node outside the query returns
Suma+ba + b00
Minimummin⁡(a,b)\min(a, b)+∞+\infty, or any value above every input
Maximummax⁡(a,b)\max(a, b)−∞-\infty, or any value below every input
Greatest common divisorgcd⁡(a,b)\gcd(a, b)00, since gcd⁡(0,x)=x\gcd(0, x) = x
XORa ^ b00

The middle column is the combine rule, and it decides whether an answer can be stored at all. A query combines whichever nodes happen to cover its range, so how the values are grouped depends on where the node boundaries fall. For the range [1, 6), the tree combines the leaf holding 2 with the node [2, 4), which already combined 4 and 5, and the node [4, 6), which combined 1 and 1. The answer has to equal what combining the five values one after another from the left would give, and in general it has to come out the same however the range is cut into pieces.

That holds when the rule is associative: combining three neighbouring pieces gives the same result whether the first two or the last two are combined first. For example, min⁡(min⁡(2,4),1)\min(\min(2, 4), 1) and min⁡(2,min⁡(4,1))\min(2, \min(4, 1)) are both 1.

Subtraction is not associative, since (2−4)−1=−3(2 - 4) - 1 = -3 and 2−(4−1)=−12 - (4 - 1) = -1. A tree that combined its children by subtracting would give answers that depend on where the range happened to be cut.

The last column is the rule's identity: the value that changes nothing when it is combined with any other, as 0 does in a sum. A node outside the query returns it, so the caller can combine the answers of its two children without checking whether one of them was outside.

The same query under three combine rules

The query below uses the same nodes whatever they store. Switch between sum, min and max: the split stays where it is and every stored value changes. The third preset is the array of free hotel rooms from the next part, as a tree of maximums.

Each node stores
a[0]3
a[1]2
a[2]4
a[3]5
a[4]1
a[5]1
a[6]5
a[7]3

The sum of [1, 6) is 13. Nodes used whole: 3. Nodes visited: 9 of 15.

Adding the values directly gives 13.