Fenwick trees for prefix sums and updates · 3 of 3 Advanced
Coordinate compression
Index a Fenwick tree by value instead of by position, replacing large values by their ranks among the values that occur.
- Custom Comparators and Coordinate Compression Its Coordinate Compression section compresses values by sorting and binary search, with two worked problems. usaco.guide (opens in a new tab)
- Point Update Range Sum Its Inversion Counting section solves the count on this page with a binary indexed tree, and its problem list has Salary Queries and several inversion problems. usaco.guide (opens in a new tab)
- 树状数组 Range add with range sum, two-dimensional trees, the k-th smallest value by binary lifting, and counting inversions with a tree indexed by value. oi-wiki.org (opens in a new tab)