Fenwick Update and Query
Query walks i to i minus lowbit(i). Update walks i to i plus lowbit(i).
Fenwick Tree: Sum of the first 7
Cell 7 covers 7 to 7 and holds 2. Add it: sum 2. Then jump to 7 - 1 = 6.
Cost
- Best
- O(log n)
- Average
- O(log n)
- Worst
- O(log n)
- Space
- O(n)
Before this
Taught by the same lesson
Fenwick Tree covers these too, in the same run.