2002. Add to a Whole Range, Read One Position

An array of n zeros is given, numbered from 1. Then q operations arrive:

add l r v add v to every position from l to r inclusive get i print the current value at position i

Print one line for each get.

add 1 3 2 -> 2 2 2 0 0 get 2 -> 2 add 2 5 3 -> 2 5 5 3 3 get 3 -> 5 get 5 -> 3

## What most people try first

Walk the range and add v to each position. That is O(r - l + 1) per update, so 2 * 10^5 updates each covering the whole array cost 4 * 10^10 steps.

A difference array, from problem 721, makes the update two writes instead. But it recovers a value with a running total from the start, which is O(n) per get. Once again one operation is cheap only because the other is not.

## The two ideas compose

This is the previous problem run backwards, and the combination is the point.

Keep a Fenwick tree over the DIFFERENCE array d, where d[i] is how much position i differs from position i - 1. Then:

add l r v: d.add(l, v); d.add(r + 1, -v) two point updates get i: return d.pre(i) one prefix sum

because the value at i is exactly d[1] + d[2] + ... + d[i], which is what a prefix sum of the difference array means.

So a structure that does point-update and range-query becomes one that does range-update and point-query, purely by changing what the array holds. No new data structure is written.

## Why it is correct

Adding v across l .. r changes the step up at l and the step back down just after r. Everything strictly inside is unchanged, because both its neighbours moved by the same v. So exactly two differences change however wide the range is, and the prefix sum through i picks up v if and only if l <= i <= r.

## The index that must exist

When r is n, the second write lands at n + 1. That position is never read, but the tree must be allocatable there, so size it for n + 1 rather than n. Sizing it n and not guarding the write is a crash that only happens on inputs whose last update reaches the end.

## Overflow

2 * 10^5 updates of 10^9 stacked on one position reach 2 * 10^14, so the value needs 64 bits. Two such updates reach 2 * 10^9, which still FITS in a signed 32 bit integer, since the limit is 2147483647; it is the two hundred thousandth that does not.

## Cost

O(q log n), about 3.6 * 10^6 steps at the limits.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ l ≤ r ≤ n` - `-10^9 ≤ v ≤ 10^9` - `1 ≤ i ≤ n` - every position starts at `0`