树状数组

树状数组

原理

树状数组可以在O(logn)的时间复杂度内计算前缀和。相比于前缀和数组和原数组，树状数组相当于两者进行了权衡。即满足单点修改，区间查询。使用差分数组可以使得树状数组在差分数组上计算，这样可以获得区间修改，单点查询的功能。

• 前缀和数组计算前缀和为O(1)，修改操作之后重新计算前缀和时间复杂度为O(n)。
• 原数组计算前缀和为O(n)，修改操作只需要O(1)的时间复杂度不用重新计算。
• 树状数组计算前缀和为O(logn)，修改操作重新计算数组的时间复杂度也为O(logn)。

树状数组的原理是将查询区间的右端点x（左端点一般为1）按照二进制展开，对于任一数字x都可以通过2的幂组合，从而快速的查询当前前缀和是多少。比如位置7的前缀和等于7 + 6 + 4位置数组之和，只需要log次操作就可以得到。

具体原理可以看下图：

在差分数组上建立树状数组，其中add操作和sum操作不变，但是由于是差分数组，对一个区间[l,r] + C相当于对差分数组add(l, c) && add(r + 1, -c)。如果求某个位置上的数字，相当于sum(x)。

另外，树状数组还可以进行区间修改，区间和查询。需要推导一下公式，当然线段树也可以很好的完成这项操作。

模板

int n;//和需要求前缀和的数组大小相等

//lowbit操作，得到当前数字二进制位的最后一个1
int lowbit(int x)
{
    return x & -x;
}

//add操作，在某一位置 + c之后，更新所有需要变化的树状数组位置
void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

//sum操作，求某一个位置x的前缀和
int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

//差分数组与树状数组结合
int main()
{
    int l, r, c;
    cin >> l >> r >> c;
    add(l, c), add(r + 1, -c);

    int x;
    cin >> x;
    cout << sum(x) << endl;
}

例题

LC.1505 最多K次交换相邻数位后得到的最小整数（困难）

AW.242 一个简单的整数问题（简单）