Implement Fenwick Tree (Binary Indexed Tree) for: (1) Point update, prefix sum query, (2) Range sum using two BITs, (3) Find k-th element (binary lifting on BIT). Compare with segment tree: when to use BIT (simpler, faster, less memory) vs segment tree (more flexible). Solve: count inversions in array using BIT in O(n log n).
