Add to every value in a range
So far, an update has changed one value. A range update changes every value in a range at once, such as "add 3 to positions 2 to 7". A Fenwick tree over a difference array handles range additions when each question is about a single position. Here both the update and the question are about ranges: add to a range, and ask for the sum of a range.
Take the same eight values as on the earlier pages, this time in a tree of sums:
The direct way to add 3 to the range [2, 8) is six point updates, one for each position. In general that is up to point updates of steps each for one range update, slower than writing the values into a plain array. With 200,000 range updates on 200,000 values, it comes to leaves to change.
A range query never visits every leaf of its range. It stops at the nodes that are inside the range, here [2, 4) and [4, 8), because each of them already holds the answer for everything below it. A range update can stop at the same nodes, provided it does two things at each of them:
- It corrects the node's own sum. Every value below the node grows by 3, so the sum grows by 3 times the length of the node:
[2, 4)goes from 9 to , and[4, 8)goes from 10 to . - It leaves a note on the node saying that everything below still has to receive . This note is called a lazy tag, or just a tag.
The nodes above them, which are only partly inside the range, are recomputed from their children as in a point update: [0, 4) becomes and the root becomes . A direct count agrees, since six values grew by 3 and .
[2, 8). The two tagged nodes and the nodes above them are correct. The faded nodes below the tags still hold their old sums.Some nodes of the tree are now out of date, which has not happened on the earlier pages. It is safe because of where they are. Every node from the two tagged ones upward holds the correct sum, so a query that stops at or above them is answered correctly: the sum of the whole array is 42, and the sum of [4, 8) is 22. The out-of-date nodes all lie below a tag, and the tag records what they are missing. So a tagged node's own sum is up to date, and its tag is what its children have not received yet.
Push a tag down before going below it
An operation that has to go below a tagged node first pushes the tag down. Each of the two children receives the waiting addition as if it had been inside the original update: its sum grows by the amount times its length, and it gets a tag of its own. Then the parent's tag is cleared.
Take the sum of [5, 7) after the update above. The walk reaches [4, 8), which is partly inside the query, and pushes its tag: [4, 6) goes from 2 to , and [6, 8) goes from 8 to . Both of those are partly inside the query too, so each pushes its new tag on to its two leaves, which become 4, 4, 8 and 6. The query then uses the leaves [5, 6) and [6, 7) and returns .
Two additions that reach the same node add up in its tag: a node tagged that receives is tagged .
Updates have to push as well, not only queries. Start again from the original tree, and suppose we add 3 to [4, 8) and then add 5 to [4, 6). The second update goes below the tagged node [4, 8), changes [4, 6), and on its way back recomputes [4, 8) from its two children. If the were still waiting on [4, 8) at that moment, the children would not include it, and the recomputed sum would be : the new sum of [4, 6) plus the stale 8 of [6, 8). The correct sum is 32, because the values 1, 1, 5 and 3 gain 3 each and the first two gain 5 more, which gives 9, 9, 8 and 6.
A push is a constant amount of work, and it happens only at nodes that the operation visits anyway. A range add and a range sum therefore visit the same nodes as a plain query, at most four per level, and both cost .
Add to ranges and watch the tags move
The widget starts on the example above. The Add button puts the on the tree. Then make the range smaller and press Query: the tags move down only along the path that the query needs. On the third preset, pressing Add twice stacks two additions on one node.
Range add and range sum in code
The program keeps a second array, tag, beside tree. Two small functions, apply and push, do the new work, and the update and the query call them.
def build(v, lo, hi):
if hi - lo == 1:
tree[v] = nums[lo]
return
mid = (lo + hi) // 2
build(2 * v, lo, mid)
build(2 * v + 1, mid, hi)
tree[v] = tree[2 * v] + tree[2 * v + 1]
def apply(v, lo, hi, x): # add x to every value in [lo, hi)
tree[v] += x * (hi - lo)
tag[v] += x
def push(v, lo, hi):
if tag[v]:
mid = (lo + hi) // 2
apply(2 * v, lo, mid, tag[v])
apply(2 * v + 1, mid, hi, tag[v])
tag[v] = 0
def range_add(v, lo, hi, left, right, x): # add x to nums[left:right]
if right <= lo or hi <= left:
return
if left <= lo and hi <= right:
apply(v, lo, hi, x)
return
push(v, lo, hi)
mid = (lo + hi) // 2
range_add(2 * v, lo, mid, left, right, x)
range_add(2 * v + 1, mid, hi, left, right, x)
tree[v] = tree[2 * v] + tree[2 * v + 1]
def range_sum(v, lo, hi, left, right): # sum of nums[left:right]
if right <= lo or hi <= left:
return 0
if left <= lo and hi <= right:
return tree[v]
push(v, lo, hi)
mid = (lo + hi) // 2
return (range_sum(2 * v, lo, mid, left, right) +
range_sum(2 * v + 1, mid, hi, left, right))
nums = [3, 2, 4, 5, 1, 1, 5, 3]
n = len(nums)
tree = [0] * (4 * n)
tag = [0] * (4 * n)
build(1, 0, n)
range_add(1, 0, n, 2, 8, 3)
print(range_sum(1, 0, n, 5, 7)) # 12
print(range_sum(1, 0, n, 0, n)) # 42The program prints 12 and 42.
apply is what happens to a node that receives an addition, whether from an update that stops there or from the push of its parent: its sum grows by x times its length, and x is added to its tag.
push applies a node's tag to both children and clears it. range_add and range_sum call it just before they go into the children, so no function reads or changes a node while a tag is waiting above it.
range_add ends by recomputing the node from its children, like a point update. The program adds 3 to [2, 8) and then prints the sum of [5, 7) and of the whole array, which are the 12 and 42 worked out above.
A leaf gets a tag from apply like any other node, but that tag is never pushed. A leaf is always inside or outside a range, never partly inside, so both functions return before they reach push.
For a tree of minimums or maximums, the sums become min or max as on the first page, and apply loses its multiplication: adding x to every value of a range raises its minimum by x once, whatever the length of the range.
Two kinds of update in one tag
A tag has to describe everything that is still waiting to happen below a node. With additions alone, one number is enough, because additions add up. When a problem has a second kind of range update, one number is no longer enough.
You keep an array of values and answer queries. 1 a b x adds to every value in positions through . 2 a b x sets every value in positions through to . 3 a b asks for the sum of positions through .
Print the answer to every sum query.
Constraints
Sample · Input
6 5 2 3 1 1 5 3 3 3 5 1 2 4 2 3 3 5 2 2 4 5 3 3 5
Output
7 11 15
All three sum queries of the sample ask about positions 3 to 5, which are highlighted here:
A set on its own would be simple. The tag would be the value that everything below has to become, and a node of length that is set to has the sum . The difficulty is that sets and adds can reach the same node, and then their order matters: "add 2, then set to 5" leaves every value at 5, and "set to 5, then add 2" leaves every value at 7.
We write a tag as a pair with one fixed meaning: first set every value below to , if the tag has an , and then add to every value below. Any sequence of updates that piles up on a node can be brought into this form, by two rules:
- A new set to replaces the whole tag by . Whatever was waiting no longer matters, because every value below becomes .
- A new add of turns into . The set, if there is one, still happens first.
For example, a node with no tag that receives "add 2" has the tag . If "set to 5" arrives next, the tag becomes , and if another "add 2" follows, it becomes , which reads "set to 5, then add 2".
A push hands the pair to each child as a set followed by an add, and each child takes it into its own tag by the same two rules.
def build(v, lo, hi):
if hi - lo == 1:
tree[v] = nums[lo]
return
mid = (lo + hi) // 2
build(2 * v, lo, mid)
build(2 * v + 1, mid, hi)
tree[v] = tree[2 * v] + tree[2 * v + 1]
def apply(v, lo, hi, s, a): # set the whole node to s (if any), then add a
old_s, old_a = tag[v]
if s is not None: # a set replaces the old tag
tree[v] = s * (hi - lo)
old_s, old_a = s, 0
tree[v] += a * (hi - lo)
tag[v] = (old_s, old_a + a)
def push(v, lo, hi):
s, a = tag[v]
if s is not None or a:
mid = (lo + hi) // 2
apply(2 * v, lo, mid, s, a)
apply(2 * v + 1, mid, hi, s, a)
tag[v] = (None, 0)
def change(v, lo, hi, left, right, s, a):
if right <= lo or hi <= left:
return
if left <= lo and hi <= right:
apply(v, lo, hi, s, a)
return
push(v, lo, hi)
mid = (lo + hi) // 2
change(2 * v, lo, mid, left, right, s, a)
change(2 * v + 1, mid, hi, left, right, s, a)
tree[v] = tree[2 * v] + tree[2 * v + 1]
def total(v, lo, hi, left, right):
if right <= lo or hi <= left:
return 0
if left <= lo and hi <= right:
return tree[v]
push(v, lo, hi)
mid = (lo + hi) // 2
return total(2 * v, lo, mid, left, right) + total(2 * v + 1, mid, hi, left, right)
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
nums = [int(x) for x in data[2:2 + n]]
tree = [0] * (4 * n) # sum of each node's range
tag = [(None, 0)] * (4 * n) # (s, a): set to s unless s is None, then add a
build(1, 0, n)
out = []
pos = 2 + n
for _ in range(q):
kind, left, right = int(data[pos]), int(data[pos + 1]) - 1, int(data[pos + 2])
if kind == 3:
out.append(total(1, 0, n, left, right))
pos += 3
continue
x = int(data[pos + 3])
pos += 4
if kind == 1:
change(1, 0, n, left, right, None, x) # add x
else:
change(1, 0, n, left, right, x, 0) # set to x
print("\n".join(map(str, out)))On the sample input the program prints 7, 11 and 15.
apply takes a pair and carries out both steps on one node. A set, if there is one, makes the node's sum times its length and resets the tag, and the add then raises the sum by times the length. An add, type 1 in the problem, calls it with None in place of a set, and a set, type 2, calls it with .
Other combinations of range updates follow the same plan. A lazy segment tree needs three things from its updates:
- a tag with one fixed form that can describe any sequence of updates waiting on a node;
- a rule for taking a new update into an existing tag;
- a way to correct a node's stored answer from the tag and the length of the node alone, without looking at the values below.
Some updates cannot meet the third requirement. The Segment tree beats page takes one of them.
Cost with lazy tags
- Range add
- The nodes a query visits, with extra work for each push.
- Range sum
- A query that pushes each tag it passes, per push.
- Range set and add in one tag
- Taking an update into a pair is .
- Memory
- entries for the sums and for the tags.
Common mistakes with lazy tags
Going below a tagged node without pushing its tag.
- Where it breaks
- After adding 3 to
[2, 8), the sum of[5, 7)reads the old leaves 1 and 5 and returns6. The answer is12. - The fix
- Call
pushbefore every step into a node's children, in queries and in updates.
Adding the amount once to a sum node.
- Where it breaks
- Adding 3 to
[4, 8)makes that node hold13. Four values each gained 3, so it should hold22. - The fix
- Add times the node's length to a sum. A minimum or a maximum gains once.
Leaving a node's sum alone after its children change.
- Where it breaks
- After adding 3 to
[2, 8), the root still holds24, and the sum of the whole array should be42. - The fix
- Recompute the node from its two children after the recursive calls return.
Keeping the old addition when a set arrives.
- Where it breaks
- Running
1 2 3 2,2 2 3 5and3 3 3on 2, 3, 1, 1, 5, 3 prints7. Position 3 was set to 5 after the add, so the answer is5. - The fix
- A new set replaces the whole tag, so the waiting add starts again at 0.
Recall After adding 3 to `[2, 8)`, which tag does the sum of `[2, 3)` push, and what does it return?
Only the tag on [2, 4), because the query has to go below that node to reach [2, 3). The push gives each child , so [2, 3) holds and the query returns 7. The tag on [4, 8) stays where it is, since the query never enters that node.