The problem
Write a Fenwick tree (lesson 3) for n values that all start at 0. Positions count from 0, as in a Python list. add(i, v) adds v to position i, prefix(i) is the total of the first i values, and total(l, r) is the total of a[l:r].
f = Fenwick(8)
f.add(0, 5); f.add(2, 7); f.add(5, 1)
f.prefix(3) # 12: positions 0, 1, 2
f.total(2, 6) # 8
f.prefix(0) # 0
The lesson’s tree counts positions from 1, so add 1 to a position inside your class.
Limits
- Up to 100,000 positions and 100,000 operations, mixed. Every operation should cost O(log n).
Builds on RNGQ-3 Fenwick tree.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
6 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Last position | Not run | |
| 3 | Adds pile up | Not run | |
| 4 | Empty range | Not run | |
| 5 | Every position | Not run | |
| 6 | 100,000 operations | Not run |