Template. Binary Index Tree

Fendwick Tree，區間查詢和，支援修改。

Code

#define maxn 1000
int tree[maxn + 1], num[maxn + 1];
void init() {
    memset(tree, 0, sizeof(tree));
    for (int i = 1; i <= maxn; i++)
        for (int j = i; j <= maxn; j += i & -i)
            tree[j] += num[i];
}
int query(int i) {
    int ans = 0;
    for (; i; i -= i & -i)
        ans += tree[i];
    return ans;
}
void modify(int i, int d) {
    for (; i <= maxn; i += i & -i)
        tree[i] += d;
}