AlgoScope

Fenwick Update and Query

Query walks i to i minus lowbit(i). Update walks i to i plus lowbit(i).

Range queries, algorithm, advanced
Adding cell 7, 2. The sum is 2.active 7-703152531144510627308i
Adding cell 7, 2. The sum is 2.active 7-703152531144510627308i

Fenwick Tree: Sum of the first 7

Decision, step 2 of 5

Cell 7 covers 7 to 7 and holds 2. Add it: sum 2. Then jump to 7 - 1 = 6.

How fenwick tree works

Cost

Best
O(log n)
Average
O(log n)
Worst
O(log n)
Space
O(n)

Taught by the same lesson

Fenwick Tree covers these too, in the same run.