Add to a range and read one value
On the main page a change touched one position and a question covered a range. The next problem is the other way round: a change adds an amount to a whole range of positions, and a question asks for one value.
You get an array of integers and queries. A query 1 a b u adds to every value at positions through . A query 2 k asks for the current value at position .
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 3 3 2 4 5 1 1 5 3 2 4 1 2 5 1 2 4
Output
5 6
In the sample, position 4 starts at 5. The second query adds 1 to positions 2 through 5, so position 4 then reads 6.
Adding to each position of the range costs up to writes per query, which is writes at these limits. A difference array brings a range addition down to two writes, but it turns the differences back into values with one pass over the whole array, which pays off only when every addition comes before every read. Here reads and additions alternate.
Recall how a difference array records a range addition. diff starts as all zeros. With positions numbered from 1, as on the main page, adding to positions through makes two writes: at position , and at position . The amount added to a position so far is then the running sum of diff up to that position. Here is the sample after its query 1 2 5 1:
The running sum is 1 from position 2, where the was written, to position 5, and 0 again from position 6, where the cancels it. Position 4 reads its starting value plus its running sum, .
Keep the difference array in a Fenwick tree
A plain difference array is turned into values by one pass at the end. Now a value can be asked for at any moment, and a pass for each read would cost up to additions again. A read needs less than a full pass, though. The running sum of diff up to position is a prefix sum of diff, and each of the two writes is an addition at one position. Those are the two operations of a Fenwick tree, so we keep diff in a tree and the starting values, which never change, in a plain array nums:
- A query
1 a b uadds at position and at position . - A query
2 kprintsnums[k]plus the prefix sum of the tree up to position .
When , the second write would go to position , which is past the end of the tree. The loop in add stops before it writes anything, and that is correct: no position after needs the addition cancelled, so the tree needs no cell for position .
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())) # the starting values
tree = [0] * (n + 1) # diff, kept in a Fenwick tree
out = []
for _ in range(q):
query = list(map(int, input().split()))
if query[0] == 1: # add u to positions a..b
_, a, b, u = query
add(tree, a, u)
add(tree, b + 1, -u)
else: # the value at position k
k = query[1]
out.append(nums[k] + prefix(tree, k))
print("\n".join(map(str, out)))On the sample input the program prints 5 and 6.
The functions prefix and add are the ones from the main page, unchanged. All that differs is the array they are applied to, which is now diff.
Read a value as a prefix sum of the differences
The widget's values are diff for the sample after the query 1 2 5 1: at position 2 and at position 6. With the operation set to Prefix sum at position 4, the loop reads cell 4 alone, which covers positions 1 to 4 and holds 1, so position 4 reads . At position 6 it reads cells 6 and 4, , and position 6 keeps its starting value.
With the operation set to Point add, you can make a range addition of your own in two steps: add at the first position of the range, then at the position after its last.
Cost of range additions and point reads
- Adding to each position of the range
per addition - Up to 200,000 writes for one query, for 200,000 queries.
- Plain `diff`, one pass per read
per read - Two writes per addition, but each read adds up to 200,000 entries of
diff. - `diff` in a Fenwick tree, range addition
- Two point adds, at most 18 cells each.
- `diff` in a Fenwick tree, point read
- One prefix sum, at most 17 cells, plus the starting value.
- Memory
- The tree and the plain array of starting values.
When both the addition and the sum cover ranges, one tree is not enough. The cp-algorithms page in Further reading does it with two Fenwick trees, and a segment tree does it with lazy propagation.
Common range addition mistakes
Writing the cancelling at position instead of .
- Where it breaks
- On the sample,
1 2 5 1then writes the at position 5, and position 5 reads1instead of2: the range lost its last position. - The fix
- Write at , the first position after the range.
Printing the prefix sum of the tree without the starting value.
- Where it breaks
- After
1 2 5 1, the query2 4prints1, the amount added to position 4, instead of6. - The fix
- Print
nums[k]plus the prefix sum up to position .
Recall After the queries `1 2 5 1` and `1 4 8 2` on the sample, which entries of `diff` are not 0, and what does position 6 read?
diff holds at position 2, at position 4 and at position 6. The of the second query belongs at position 9, which is past the end, so it is not written. The entries up to position 6 add up to , and position 6 reads . That agrees with the queries: only the second range covers position 6.