Binary Indexed Trees

[henix]

spoj:

http://codeforces.com/blog/entry/619 http://www.quora.com/CodeChef/What-are-some-suggestions-for-problems-where-Binary-Indexed-Tree-BIT-Fenwick-Tree-is-the-primary-concept

理解：

http://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a

[henix]

一般：更新一点，求前缀和

roba：《用树状数组解决区间查询问题》。用两个树状数组实现类似线段树的效果。可解决 poj 3468 A Simple Problem with Integers

[henix]

poj 2828：用树状数组找前缀和为 sum 的第一个 i

int first_sumto(int ar[], int es) {
    int level = msb(ar[0]);
    int idx = 0;
    int sum = 0;
    while (level > 0) {
        idx += level;
        if (idx > ar[0] || sum + ar[idx] >= es) {
            idx -= level;
        } else {
            sum += ar[idx];
        }
        level >>= 1;
    }
    return idx + 1;
}

[henix]

poj 2828 Buy Tickets 可以用树状数组求 0 - 1 序列中第 k 个 1 的位置，并支持动态更新

[henix]

更新一片，求点可以 improve 到都是 log n （而不是 2 log n）