Medium · Fenwick Tree
Understand → Visualise → Practice.
Process `sum,left,right` inclusive range queries and `set,index,value` updates; return the answers to sum queries in order.
A Fenwick tree keeps prefix sums that can be updated in O(log n). A range sum is prefix(right) − prefix(left − 1).
Add each starting value into a 1-indexed Fenwick array, moving up with index += index & −index.
For set i to v, add v − current[i] to the tree, then remember v as the current value.
For sum l..r, return prefix(r) − prefix(l − 1), walking down with index −= index & −index.
O((n + q) log n) time and O(n) space.
A set must add the difference from the old value, not the new value itself.
Read the full guide first: Fenwick Trees and Segment Trees.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.