Fenwick trees for prefix sums and updates · 1 of 3 Advanced
Point updates and prefix sums
Keep range sums fast while single values change, by storing the sums of blocks whose lengths are the lowest set bits of their end positions.
Books1
Links3
- Point Update Range Sum Segment trees and binary indexed trees on Dynamic Range Sum Queries, then finding the k-th element, counting inversions and a problem list that includes Distinct Values Queries. usaco.guide (opens in a new tab)
- Fenwick Tree Defines the cells through a function g(i) with indices from 0, then gives the version with indices from 1 used here, the linear-time build, 2D trees and range updates with range sums using two trees. cp-algorithms.com (opens in a new tab)
- Binary Indexed Trees Reads a single value without the plain copy, scales the whole tree and finds the position with a given prefix sum by descending the bits. topcoder.com (opens in a new tab)