Fenwick Tree Range Sum

Extend a Fenwick tree over n 1-indexed slots (initially all zero) with a range-sum query. update(int i, long long d) (d fits in a 64-bit integer: long long in C++; Python ints are arbitrary precision; JavaScript numbers are exact integers up to 2^53, which covers every value these tests produce) adds d to slot i. query(int i) returns the prefix sum of slots 1..i (0 when i is 0). range(int l, int r) must return the sum of slots l..r inclusive, computed as query(r) - query(l - 1) so that slot l itself is included.

Operations arrive as U i d (apply an update) and R l r (print the sum of slots l..r). Indices are 1-indexed with 1 <= l <= r <= n; l is not always 1.

Example: Starting from f.update(1, 3), f.update(4, 2), f.range(2, 4) is query(4) - query(1) = 5 - 3 = 2, correctly picking up only slot 4's contribution while slots 2 and 3 stay at 0. Contrast f.range(1, 4), which is query(4) - query(0) = 5 - 0 = 5 and does include slot 1.

Tests include a case with n up to 2*10^5 and q up to 2.2*10^6, so each update/range must run in O(log n), not O(n).

Input format: each test in tests/*.in is laid out as:

• Line 1: the mode letter L.
• Line 2: n q, the tree size and the number of operations; slots are 1-indexed.
• Next q lines: one operation each, either U i d (add d to slot i) or R l r (print the sum of slots l..r).

A performance test is instead the single line G 200000 2200000 4242 (mode G): the harness generates the q operations itself from the seed and compares one combined hash of every range answer, so your update/range see the same calls as in L mode.

Test 02.in reads:

L
12 6
U 4 10
U 9 1
U 12 5
R 4 9
R 9 9
R 2 12

This is size 12 with 6 operations: three point updates, then range sums including the single-slot range R 9 9.

Where you'll use it:

• 315. Count of Smaller Numbers After Self
• 327. Count of Range Sum