Range sums on an array that changes
A prefix array answers each range sum with one subtraction, on the condition that the array stays fixed between questions. This page drops that condition: values change, and range sums are asked for in between the changes.
You get an array of integers and queries. A query 1 k u sets the value at position to . A query 2 a b asks for the sum of the values at positions through .
The first line holds and , the second the values, and each further line one query. Print the answer to every query of the second kind.
Constraints
Sample · Input
8 4 3 2 4 5 1 1 5 3 2 1 4 2 5 6 1 3 1 2 1 4
Output
14 2 11
The sample's array has eight values. The problem numbers positions from 1, and so does this page:
The first query asks for positions 1 to 4, which hold , and the second for positions 5 and 6, which hold . The third sets position 3 to 1. The last query asks for positions 1 to 4 again and now gets .
There are two simple ways to store the array, and each makes one kind of query slow. With the plain array, a change is one write, but a sum adds up to values. With a prefix array, a sum is one subtraction, but a change has to rewrite every entry that includes the changed position. Here is prefix before and after position 3 changes from 4 to 1:
prefix[i] is the sum of the first i values. The highlighted entries are the ones the change rewrote.Six of the nine entries changed, and a change at position 1 would rewrite all of them except prefix[0]. So whichever array we choose, one kind of query can cost steps. The problem allows 200,000 values and 200,000 queries:
At about simple steps a second in C++, that is 400 seconds of work against a one-second limit, and a loop written in Python is about ten times slower.
A Fenwick tree, also called a binary indexed tree, is a third way to store the array. It keeps the sums of certain blocks of positions, chosen so that every prefix is made of a few blocks and every position lies in only a few blocks. A prefix sum then adds a few stored numbers, and a change rewrites a few. With 200,000 values, a prefix sum reads at most 17 stored numbers and a change rewrites at most 18. The blocks nest inside one another, so they form a tree, but the whole structure is stored as one array.
Blocks whose lengths are powers of two
To choose the blocks, start from one prefix, the first 7 positions. Seven is , so the prefix can be cut into a block of 4 positions, then a block of 2, then a block of 1:
If the sums of those three blocks are stored, the sum of the first 7 values is , read from three stored numbers in place of seven values.
Every prefix can be cut this way, because every length is a sum of distinct powers of two. Those powers are the 1 bits of its binary form. Taking the largest power first:
- 7 is
111, or : positions 1 to 4, positions 5 to 6, position 7. - 6 is
110, or : positions 1 to 4, positions 5 to 6. - 5 is
101, or : positions 1 to 4, position 5. - 4 is
100: positions 1 to 4.
The four cuts share blocks: positions 1 to 4 are in all of them, and positions 5 to 6 are in two.
Now look at the last block of each cut. It ends at the last position of the prefix, and its length is the smallest power of two in the sum, the rightmost 1 bit of the prefix length. A bit that is 1 is called a set bit, so this power is the value of the lowest set bit of the length: 1 for 7, 2 for 6, 1 for 5 and 4 for 4. From here on, the lowest set bit of a number means this value, a power of two, and not the place of the bit.
Every earlier block of a cut is itself the last block of a shorter cut. In the cut for 7, positions 5 to 6 are the last block of the cut for 6, and positions 1 to 4 are the last block of the cut for 4. So it is enough to store the last block of every cut, which is one block per position.
Definition
tree[i] is the sum of the block that ends at position i and whose length is the lowest set bit of i.
We call tree[i] cell i, and say that it covers the positions of its block. Six is 110 and its lowest set bit is 2, so cell 6 covers positions 5 and 6.
The eight cells for the sample
In code, the lowest set bit of i is i & -i. In eight bits, 12 is 00001100, and -12, which is stored as , is 11110100. The two agree at the lowest set bit of 12 and at the zeros below it, and differ at every bit above it, so the AND keeps that one bit: 00000100, which is 4. The Bit manipulation lesson shows why -i has this form, in its Deeper read on x & -x. Cell i therefore covers positions i - (i & -i) + 1 through i. Here are the cells for the sample's eight values:
Cell i | Binary | i & -i | Positions covered | tree[i] |
|---|---|---|---|---|
| 1 | 0001 | 1 | 1 | 3 |
| 2 | 0010 | 2 | 1 to 2 | 5 |
| 3 | 0011 | 1 | 3 | 4 |
| 4 | 0100 | 4 | 1 to 4 | 14 |
| 5 | 0101 | 1 | 5 | 1 |
| 6 | 0110 | 2 | 5 to 6 | 2 |
| 7 | 0111 | 1 | 7 | 5 |
| 8 | 1000 | 8 | 1 to 8 | 24 |
Every odd cell covers one position, its own. A cell whose number is a power of two, such as 4 or 8, covers everything from position 1 up to itself. tree has one entry for each position from 1 to . tree[0] is not used, because 0 has no set bit and so no block can end there.
Read a prefix sum from the tree
Write prefix(i) for the sum of the first i values, the number that prefix[i] holds in the prefix array above. With positions numbered from 1, those are positions 1 to i. To compute prefix(i) from the tree, we walk the cut of the first i positions from its last block back to its first. For prefix(7):
- Cell 7 covers position 7 alone, so add
tree[7], which is 5. The positions still to add end at . - Cell 6 covers positions 5 and 6, so add
tree[6], which is 2. The positions still to add end at . - Cell 4 covers positions 1 to 4, so add
tree[4], which is 14. Now , and no position is left.
t[i] is short for tree[i]. The highlighted cells 7, 6 and 4 are the three blocks of prefix(7).The total is . At each step the cell number lost its lowest set bit: 7 is 111, 6 is 110, 4 is 100, and then comes 0. Subtracting i & -i from i clears that bit. The loop stops when no bit is left:
def prefix(tree, i): # sum of positions 1..i
total = 0
while i > 0:
total += tree[i]
i -= i & -i
return total
tree = [0, 3, 5, 4, 14, 1, 2, 5, 24]
print(prefix(tree, 7))The last two lines run the function on the sample's cells, with a 0 in the unused entry tree[0], and print 21.
The loop runs once for each 1 bit of i. The smallest number with 18 one bits is , which is more than 200,000, so with 200,000 values a prefix sum reads at most 17 cells.
A range sum is two prefix sums. Positions a through b are the first b values without the first a - 1:
The sample's second query, positions 5 to 6, is prefix(6) - prefix(4), or . Its first query starts at position 1 and subtracts prefix(0), the sum of no values. The loop returns 0 for it without reading a cell.
Add to one position
When a value changes, every cell that covers its position has to change with it. Take position 5. In the figure, the bars under position 5 are cells 5, 6 and 8:
Cell 5 covers position 5 alone, cell 6 covers positions 5 and 6, and cell 8 covers all eight. Cell 7 comes after position 5 but covers only position 7, so it stays as it is.
The loop that visits these cells starts at the changed position and adds the lowest set bit, where the prefix loop subtracted it. Five is 0101, and . Six is 0110, and . Eight is 1000, and is past the last position, so the loop stops:
def add(tree, i, delta): # add delta at position i
while i < len(tree):
tree[i] += delta
i += i & -i
tree = [0, 3, 5, 4, 14, 1, 2, 5, 24]
add(tree, 5, 2)
print(tree[5], tree[6], tree[8])The last lines add 2 at position 5 of the sample and print cells 5, 6 and 8, which have gone from 1, 2 and 24 to 3, 4 and 26.
To see why the step from 6 goes to 8, add in binary. Six is 0110. Adding its lowest set bit, 2, carries into the next place, which also holds a 1, and carries again, so the result is 1000. Cell 8 covers positions 1 to 8, which include positions 5 and 6 of cell 6. The step jumps over cell 7, whose block does not reach back to position 6.
In general the carry clears the bit that was added, so the lowest set bit of the next cell is at least twice as large and its block is at least twice as long. The blocks along the way therefore have lengths of at least 1, 2, 4 and so on. No block is longer than the array, and is more than 200,000, so the longest possible block is positions and a change touches at most 18 cells. The Deeper read at the end of this part shows that the loop visits every cell that covers the position and no other cell.
add adds delta, which can be negative. The problem's first kind of query sets a position to a new value, so the program turns it into an addition of the new value minus the old one. In the sample, position 3 goes from 4 to 1, a difference of , which is added to cells 3, 4 and 8. tree[4] drops from 14 to 11, the answer to the sample's last query. Taking the difference needs the old value, so the program keeps the current values in a plain array beside the tree.
Step through both loops
The widget holds the sample's array. With the operation set to Prefix sum, choose a position and step through the loop: each step lights one cell, shows the cell number in binary beside its lowest set bit, and shades the positions added so far.
With the operation set to Point add, choose position 3 and add to replay the sample's change. Cells 3, 4 and 8 change, and a prefix sum at position 4 then reads 11.
Deeper read: which cells the add loop visits
Call the lowest set bit of i , so that cell i covers the positions that end at i. Two facts about the cells after i make the loop correct. For i = 6, where is 2, they say that cell 7 does not reach back to position 6 and that cell 8 covers positions 5 and 6.
The first fact is that no cell strictly between i and i + L covers position i or anything before it. Such a cell is i + d with . All the bits of lie below the lowest set bit of i, so the lowest set bit of i + d is the lowest set bit of , which is at most . The block of that cell therefore starts at position i + 1 or later.
The second fact is that cell i + L covers every position that cell i covers. The bit with value is set in i, so adding carries out of it, and the lowest set bit of i + L is at least . The block of cell i + L ends positions after i and is at least long, so it starts at or before position i - L + 1, where the block of cell i starts.
A block ends at the number of its cell, so no cell numbered below the changed position covers . Now start the loop at . Cell covers , and by the second fact every later cell on the loop's path covers the block of the cell before it, so all of them cover . By the first fact, a cell that lies between two cells of the path covers nothing as far back as the earlier of the two, so it does not cover . The path is therefore exactly the set of cells that cover .
Build the tree and answer the queries
The program for Dynamic Range Sum Queries is the two functions and a loop over the queries. tree has entries, so the problem's positions are used as they are given. An array of zeros is a correct tree for an array of zeros, so the program starts from a tree of zeros and calls add once for each starting value. value[k] is the current value at position k, which a set query needs for its difference.
input = sys.stdin.readline
def prefix(tree, i): # sum of positions 1..i
total = 0
while i > 0:
total += tree[i]
i -= i & -i
return total
def add(tree, i, delta): # add delta at position i
while i < len(tree):
tree[i] += delta
i += i & -i
n, q = map(int, input().split())
value = [0] + list(map(int, input().split())) # value[k]: position k now
tree = [0] * (n + 1)
for k in range(1, n + 1):
add(tree, k, value[k])
out = []
for _ in range(q):
query = list(map(int, input().split()))
if query[0] == 1: # set position k to u
_, k, u = query
add(tree, k, u - value[k])
value[k] = u
else: # sum of positions a..b
_, a, b = query
out.append(prefix(tree, b) - prefix(tree, a - 1))
print("\n".join(map(str, out)))On the sample input the program prints 14, 2 and 11.
Cost of changes and range sums
- Plain array
per range sum - A change is one write, but a sum adds up to values.
- `prefix` array
per change - A sum is one subtraction, but a change rewrites up to entries.
- Fenwick tree, prefix sum
- One cell for each 1 bit of the position, at most 17. A range sum is two prefix sums.
- Fenwick tree, point add
- The lowest set bit at least doubles at each step, so at most 18 cells.
- Building the tree
- One
addfor each starting value. The Deeper read below builds the tree in . - Memory
- cells and the plain array of current values.
A sum query reads at most cells and a set query writes at most 18. The problem's 200,000 queries therefore visit at most cells, after a build of at most cell writes. Together that is about steps. On our laptop the Python program took under half a second for 200,000 sums that each read 34 cells.
Deeper read: build the tree in linear time
Building with one add per value writes up to 18 cells for each value. The tree can also be built with one addition per cell. Copy each value into its own cell, then go through i from 1 to and add tree[i] to the next cell that covers it, tree[i + (i & -i)], when that cell exists.
The block of cell i is position i together with the blocks of the cells that pass their totals to it: cell 8 covers position 8 and the blocks of cells 4, 6 and 7. Those cells have smaller numbers than i, so the loop has passed each of them on before it reaches i, and tree[i] is complete when it is passed on in turn.
def build(nums):
n = len(nums)
tree = [0] + nums
for i in range(1, n + 1):
j = i + (i & -i)
if j <= n:
tree[j] += tree[i]
return tree
print(build([3, 2, 4, 5, 1, 1, 5, 3]))On the sample, cell 1 passes 3 to cell 2, which becomes 5. Cell 4 starts with its own value 5 and receives that 5 from cell 2 and 4 from cell 3, which makes 14. Cell 5 passes 1 to cell 6, which becomes 2. Cell 8 starts with its own value 3 and receives 14, 2 and 5 from cells 4, 6 and 7, which makes 24. The result is the tree column of the table of cells.
Worked example
Trace the sample's queries
The trace builds the tree for the sample and runs its four queries. Each frame shows the cell being read or written in binary beside its lowest set bit. The tree is built by the linear-time method of the Deeper read above, in which each cell passes its total to the next cell that covers it.
The trace numbers values from 0 and writes ranges half-open. [2, left, right] sums the range [left, right), which is prefix(right) - prefix(left), and [1, i, value] sets the value at index i, which is position i + 1 of the tree. The sample's queries 2 1 4, 2 5 6, 1 3 1 and 2 1 4 therefore appear as [2, 0, 4], [2, 4, 6], [1, 2, 1] and [2, 0, 4].
Copy each value into the tree. Position p holds nums[p - 1], so the tree runs from 1 to 8. Next, each cell adds its total to cell i + (i & -i).
Change the example input
Current result: [14,2,11]
Sums, counts and XOR in a Fenwick tree
The cells do not have to hold sums of the array's own values. The tree needs what a prefix array needs: an operation that can be undone, because a range is one prefix with a shorter prefix taken away, and a change is applied as a difference. Subtraction undoes addition, so sums work. Counts are sums of 1s and 0s. XOR undoes itself, so a tree of XORs uses ^ in place of both + and -.
Minimums and maximums cannot be undone. Knowing the minimum of the first 6 values and the minimum of the first 4 does not give the minimum of positions 5 and 6. A change causes a second problem that the fixed prefix array never had: if the value that was the minimum of a block goes up, the new minimum is some other value of the block, and the cell kept only one number. A segment tree handles those questions.
Count the distinct values in a range
In the next problem the array itself never changes. The tree holds 1s and 0s that mark positions of the array, and those marks change while the program runs.
You get an array of integers and queries. A query a b asks how many distinct values lie at positions through .
The first line holds and , the second the values, and each further line one query. Print the answer to every query.
Constraints
Sample · Input
5 3 3 2 3 1 2 1 3 2 4 1 5
Output
2 3 3
In the sample, positions 1 to 3 hold 3, 2, 3, which is two distinct values, and positions 2 to 4 hold 2, 3, 1, which is three. Collecting the values of each range in a set costs up to steps per query, which is steps again at these limits.
A value has to count once in a range however many copies of it the range holds, so we choose one copy to count: the last one. Take the queries that end at the same position . Put a 1 at the last copy of each value among positions 1 to , and a 0 at every other position. Here are these marks for , 4 and 5:
At the values so far are 3, 2, 3. The last copy of 3 is at position 3, so position 1 holds a 0, and the 1s are at positions 2 and 3. A value occurs somewhere in positions to exactly when its last copy up to is at position or later. So the number of distinct values in positions to is the number of 1s there, which is a range sum over the marks. For the query 1 3 that sum is .
Moving from to changes at most two marks. Position gets a 1, and if its value has occurred before, the 1 at the earlier copy becomes a 0. Going from to in the figure, position 5 holds the value 2, so it gets a 1 and position 2 loses its 1. Both changes are point adds, so the marks are kept in a Fenwick tree. We sweep from 1 to , and each query is answered with one range sum at the moment reaches its right end.
The queries are not given in order of their right ends, so the program reads all of them first, sorts them by right end, and stores each answer at the place of its query in the input, for printing in that order. Reading every query before answering any is called answering the queries offline. It is possible here because no query changes the array.
input = sys.stdin.readline
def prefix(tree, i): # sum of positions 1..i
total = 0
while i > 0:
total += tree[i]
i -= i & -i
return total
def add(tree, i, delta): # add delta at position i
while i < len(tree):
tree[i] += delta
i += i & -i
n, q = map(int, input().split())
nums = [0] + list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(q)]
tree = [0] * (n + 1) # the marks
last = {} # value -> position of its 1
answers = [0] * q
r = 0
for i in sorted(range(q), key=lambda j: queries[j][1]): # by right end
a, b = queries[i]
while r < b: # move the sweep to position b
r += 1
if nums[r] in last:
add(tree, last[nums[r]], -1)
last[nums[r]] = r
add(tree, r, 1)
answers[i] = prefix(tree, b) - prefix(tree, a - 1)
print("\n".join(map(str, answers)))On the sample input the program prints 2, 3 and 3.
The sweep makes at most point adds, and each query takes two prefix sums. At 200,000 values and 200,000 queries, that is at most cell visits, plus the sorting of the queries. Mo's algorithm answers the same queries with up to about window moves at these limits, so the sweep is the faster method here.
Common Fenwick tree mistakes
Using index 0 in the tree.
- Where it breaks
- An
addat index 0 runsi += i & -iwithi = 0. That adds 0 every time, so the loop never ends. - The fix
- Number the positions from 1. If the input counts from 0, index is position .
Adding the new value instead of the difference.
- Where it breaks
- On the sample, setting position 3 from 4 to 1 by adding 1 leaves it at 5, and positions 1 to 4 sum to
15instead of11. - The fix
- Add the new value minus the old one.
Leaving the old value in the plain array after a change.
- Where it breaks
- Set position 3 to 1, then to 6. The second difference is taken from the stale 4, so it adds 2 instead of 5, and positions 1 to 4 sum to
13instead of16. - The fix
- Store the new value in the plain array on every change.
Subtracting
prefix(a)instead ofprefix(a - 1).- Where it breaks
- For
2 1 4on the sample,prefix(4) - prefix(1)gives , which leaves out position 1. The answer is14. - The fix
- Positions through are
prefix(b)minus everything before position , which isprefix(a - 1).
Answering a distinct-values query after the sweep has passed its right end.
- Where it breaks
- Sweeping all five positions of 3, 2, 3, 1, 2 first leaves the 1s at positions 3, 4 and 5. Query
1 3then counts1instead of2, because the 1 for the value 2 has moved to position 5. - The fix
- Sort the queries by right end and answer each one when the sweep reaches it.
Recall An array has 16 values. Which cells does `prefix(11)` read, and which cells does an addition at position 11 write?
Eleven is 1011. Clearing the lowest set bit gives 10 (1010), then 8 (1000), then 0, so prefix(11) reads cells 11, 10 and 8. They cover position 11, positions 9 to 10 and positions 1 to 8.
Adding the lowest set bit gives (1100), then , and is past the end. The addition writes cells 11, 12 and 16. Cell 12 covers positions 9 to 12 and cell 16 covers all sixteen.