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 and standing for the values of the two children:
| Answer for a range | Combine two children | A node outside the query returns |
|---|---|---|
| Sum | ||
| Minimum | , or any value above every input | |
| Maximum | , or any value below every input | |
| Greatest common divisor | , since | |
| XOR | a ^ b |
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, and are both 1.
Subtraction is not associative, since and . 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.
Find the first position that fits by walking down the tree
A range query starts from a range and returns a value. The tree can also be searched the other way round: given a value, find the first position that holds at least that much. The next problem asks for this.
There are hotels in a row, hotel with free rooms. Groups arrive one at a time; group needs rooms in one hotel and takes the first hotel from the left with at least free rooms, which then has fewer.
Print the hotel each group takes, numbered from 1, or 0 if no hotel has enough rooms.
Constraints
Sample · Input
8 5 3 2 4 1 5 5 2 6 4 4 7 1 1
Output
3 5 0 1 1
In the sample, the first group needs 4 rooms. Hotels 1 and 2 have 3 and 2 free rooms, so the group goes to hotel 3, which is left with 0. The second group of 4 passes hotels 1 to 4, which now have 3, 2, 0 and 1 rooms, and takes hotel 5. No hotel has 7 rooms, so the third group gets 0, and the two groups of 1 both fit into hotel 1.
Checking the hotels from the left for each group costs up to steps per group, which is steps again at the limits.
For a group that needs rooms, a tree of maximums gives a quicker test for a whole block of hotels: some hotel in a range has at least free rooms exactly when the maximum of the range is at least . With that test, a binary search over could find the first hotel that fits, by asking whether the maximum of hotels 1 to is at least . The answer can only change from no to yes as grows, which is what a binary search needs.
That is one range-maximum query per step and about 18 steps per group. The tree can do better, because it already halves its range at every node.
First we look at the root. Its maximum covers all the hotels, so if it is below , no hotel fits and the answer is 0. Otherwise we walk down from the root.
At each node we read the maximum of the left child. If it is at least , some hotel in the left half fits, and the first hotel that fits must be there, because every hotel in the left half comes before every hotel in the right half. If it is below , no hotel on the left fits, and since the node we are at does contain one, it is on the right. Either way we move to that child. The walk ends at a leaf, which is the hotel we are looking for.
[0, 4) because the left child there holds only 3, and left again to reach hotel 3.When the group moves in, the leaf loses rooms, and the maximums above it are recomputed on the way back up, as in a point update. A group costs one walk down and one walk up, which is . The binary search over separate queries costs .
def build(v, lo, hi):
if hi - lo == 1:
tree[v] = rooms[lo]
return
mid = (lo + hi) // 2
build(2 * v, lo, mid)
build(2 * v + 1, mid, hi)
tree[v] = max(tree[2 * v], tree[2 * v + 1])
def take(v, lo, hi, r): # first hotel with at least r free rooms
if hi - lo == 1:
tree[v] -= r
return lo
mid = (lo + hi) // 2
if tree[2 * v] >= r:
i = take(2 * v, lo, mid, r)
else:
i = take(2 * v + 1, mid, hi, r)
tree[v] = max(tree[2 * v], tree[2 * v + 1])
return i
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
rooms = [int(x) for x in data[2:2 + n]]
tree = [0] * (4 * n) # the most free rooms in one hotel of each node's range
build(1, 0, n)
answers = []
for r in map(int, data[2 + n:2 + n + m]):
if tree[1] < r: # no hotel has room
answers.append(0)
else:
answers.append(take(1, 0, n, r) + 1)
print(*answers)On the sample input the program prints 3 5 0 1 1.
The function take does the walk and the update in one recursion: it goes down to the leaf, subtracts there, and recomputes each node as the calls return. The main loop checks tree[1], the root, before it calls take, because the walk is only correct when some hotel fits.
The same walk answers other questions of the form "the first position where...". On a tree of sums over an array of 0s and 1s, it finds the position of the -th 1: if the left child's sum is at least , go left, and otherwise subtract that sum from and go right.
Store several values in each node
A node does not have to hold a single number. Take averages. The average of a range cannot be computed from the averages of its two halves, because the halves can have different lengths: a half with the single value 2 and a half with three values that average 6 have the overall average , while averaging the two averages gives .
If every node stores a sum and a count, though, both combine by addition, and the average of any range is its sum divided by its count. In general, a node has to store enough for its parent to be computed from its two children, even when the question asks for only part of it. The next problem needs four numbers per node.
You get an array of integers and updates. Each update k x sets position to . After each update, print the largest sum of a subarray of consecutive values; the empty subarray counts, with sum 0.
Constraints
Sample · Input
5 3 1 2 -3 5 -1 2 6 3 1 2 -2
Output
9 13 6
The sample starts from 1, 2, , 5, , and its first update, 2 6, sets position 2 to 6. After it the array is
and the subarray with the largest sum is the highlighted one, .
For an array that does not change, Kadane's algorithm finds this sum in one pass, by keeping the largest sum of a subarray that ends at the current position. Here the array changes up to 200,000 times, and one pass per update is steps. We want a tree whose root holds the answer, so that a point update repairs it in .
Suppose each node stores the largest subarray sum inside its range, and call it best. The best of a node is not just the larger best of its two children, because the best subarray can lie in three places: entirely in the left half, entirely in the right half, or across the middle. A subarray across the middle is the end of the left half followed by the start of the right half. The two pieces can be chosen separately, so the best one adds the largest sum of a suffix of the left half to the largest sum of a prefix of the right half.
So a node also stores suffix and prefix, the largest sums of a suffix and of a prefix of its range. These two need help in turn. The best prefix of a node is either a prefix of its left half, or the whole left half followed by a prefix of the right half, and the second option needs the total of the left half. The best suffix is the mirror image. That makes four numbers per node. With and for the left and the right child:
The empty subarray is allowed, so prefix, suffix and best are never negative. A leaf with the value has total equal to , and the other three equal to when is positive and to 0 otherwise.
Check the combine on the sample
suffix and the right child's prefix add up to it.In the figure, the left child covers 1, 6 and stores (7, 7, 7, 7) as its total, prefix, suffix and best. The right child covers , 5, and stores (1, 2, 4, 5). The best of the root is
def leaf(x): # (total, best prefix, best suffix, best)
return (x, max(x, 0), max(x, 0), max(x, 0))
def combine(a, b):
return (a[0] + b[0],
max(a[1], a[0] + b[1]),
max(b[2], b[0] + a[2]),
max(a[3], b[3], a[2] + b[1]))
def build(v, lo, hi):
if hi - lo == 1:
tree[v] = leaf(nums[lo])
return
mid = (lo + hi) // 2
build(2 * v, lo, mid)
build(2 * v + 1, mid, hi)
tree[v] = combine(tree[2 * v], tree[2 * v + 1])
def update(v, lo, hi, i, x):
if hi - lo == 1:
tree[v] = leaf(x)
return
mid = (lo + hi) // 2
if i < mid:
update(2 * v, lo, mid, i, x)
else:
update(2 * v + 1, mid, hi, i, x)
tree[v] = combine(tree[2 * v], tree[2 * v + 1])
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
nums = [int(x) for x in data[2:2 + n]]
tree = [None] * (4 * n)
build(1, 0, n)
out = []
for j in range(m):
k, x = int(data[2 + n + 2 * j]), int(data[3 + n + 2 * j])
update(1, 0, n, k - 1, x)
out.append(tree[1][3]) # the root's best subarray
print("\n".join(map(str, out)))On the sample input the program prints 9, 13 and 6.
combine(a, b) and combine(b, a) give different results, since a has to be the half on the left. The tree always passes the left child first, in build and in update. A combine rule does not have to give the same answer when its two sides are swapped. It does have to be associative, and this one is: each of the four numbers describes the range itself, whichever way the range was cut into pieces.
Every question in this problem is about the whole array, so the program reads the root after each update and has no query function. To answer the same question for a range, a query would combine the nodes inside the range from left to right with the same combine, and a node outside the range would return (0, 0, 0, 0), the four numbers of an empty range.
Cost with custom combine rules
- Query or point update
combines - The same nodes as for a minimum. Each combine is as long as a node stores a fixed number of values.
- First position by walking down
- One child read per level on the way down, and one node recomputed per level on the way up.
- First position by binary search over queries
- About 18 separate queries for , each .
- Memory
- nodes, each with its fixed number of values.
Common mistakes with combine rules
Testing the right child first when walking down.
- Where it breaks
- In Hotel Queries, the first group of 4 goes right at every node and ends at hotel
8, the last hotel with enough rooms, when the answer is hotel3. - The fix
- Read the left child first, and go right only when the left child's maximum is below .
Walking down without checking the root.
- Where it breaks
- For the group of 7 in the sample, every left child is too small, so the walk goes right all the way and assigns hotel
8, which has only 6 rooms. The answer is0. - The fix
- Compare the root's maximum with before the walk, and print 0 when it is too small.
Taking a node's best subarray as the larger of its children's bests.
- Where it breaks
- No node then counts a subarray longer than one value. For 1, 6, , 5, the root reads
6, and the answer is9. - The fix
- Include the subarray across the middle,
L.suffix + R.prefix.
Keeping sums in a 32-bit
intin C++.- Where it breaks
- values of add up to , which overflows and prints a wrong total.
- The fix
- Use
long longfor every field that holds a sum.
Recall In Subarray Sum Queries, what four numbers does the root store after the second update, `3 1`?
The array is now 1, 6, 1, 5, . The left half 1, 6 stores total 7, prefix 7, suffix 7 and best 7. The right half 1, 5, stores total 5, prefix 6, suffix 5 and best 6. The root combines them into total 12, prefix , suffix and best , the second answer of the sample.