Fenwick Tree (Point Update, Prefix Sum)

core

Implement a Fenwick tree (binary indexed tree) over n 1-indexed slots, initially all zero. update(int i, long long d) adds d to slot i by walking i += i & -i until i exceeds n. query(int i) returns the prefix sum of slots 1..i by walking i -= i & -i until i reaches 0; query(0) is 0.

Operations arrive as U i d (apply an update) and Q i (print the prefix sum through i). Indices are 1-indexed and always in [1, n]; d and running sums fit in a 64-bit integer (long long in C++; Python ints are arbitrary precision, so no overflow handling is needed there; JavaScript numbers are exact integers up to 2^53, which comfortably covers every value these tests produce).

Example: Fenwick f(5); f.update(1, 3); f.update(4, 2) puts 3 at slot 1 and 2 at slot 4. f.query(3) sums slots 1..3 → 3 (only slot 1 is nonzero). f.query(4) sums slots 1..4 → 5 (3 + 2).

Tests include a case with n up to 2*10^5 and q up to 6.5*10^5, so each update/query 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 Q i (print the prefix sum of slots 1..i).

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

Test 04.in reads:

This is size 10 with 4 operations: Q 1 before any update prints 0, then U 10 4 makes Q 10 print 4 while Q 1 still prints 0.

Where you'll use it:

✦ Solution & editorial unlock with the pass.