树状数组

树状数组一般用于解决插点问线和插线问点两类问题，与线段树相比，编程复杂度更低，时间空间效率都较高，但应用面没线段树宽泛。 为方便起见，一般数组下标从1开始算。以下是树状数组操作的核心代码。

int lowbit(int x) {
    return x & -x;
}
void add(int x, int v) {
    while (x > 0 && x <= N) {
        a[x] += v;
        x += lowbit(x);
    }
}
int sum(int x) {
    int ans = 0;
    while (x > 0) {
        ans += a[x];
        x -= lowbit(x);
    }
    return ans;
}

插点问线

此种情况下，a[x]表示从位置x开始往前lowbit(x)个元素的和。

• 若要将位置x的元素增加值k，则调用：add(x, k);
• 若要求区间[x,y]元素之和，则调用：sum(y) - sum(x-1);

插线问点

此时a[x]存的不是和，而是标记。

• 若要将区间[x,y]元素都增加k，则调用：add(x, k); add(y + 1, -k);
• 若要求位置x的元素值，则调用：sum(x);