title: 树状数组
date: 2019-01-28 22:05:24
categories: 算法学习
tags: 数据结构

更好的阅读体验
例1：给出一个长度为n的序到，有m个询问，每次形如l，r，求[l，r]的区间和。

法1： 暴力

• 每次询问都扫一遍。

法2： 前缀和

• 预处理O(n),每询问次O(1)时间复杂度。

法3： 线段树 & 树状数组

• 弱智。。。

[HTML_REMOVED]

例2：给出一个长度为n的序到，有m个操作，分别为询问[l，r]的区间和，和将x位置上的值增加c。

暴力前缀和行不通，每次修改都需要重新计算前缀和，这时候正解就是树状数组了。

• lowbit(x) : 等于x在二进制下最右边呢个1代表的多少。

1 对应的二进制是 -> 1      最右边呢个1对应的10进制 -> 1
2 对应的二进制是 -> 10     最右边呢个1对应的10进制 -> 2
3 对应的二进制是 -> 11     最右边呢个1对应的10进制 -> 1
4 对应的二进制是 -> 100        最右边呢个1对应的10进制 -> 4
5 对应的二进制是 -> 101        最右边呢个1对应的10进制 -> 1
6 对应的二进制是 -> 110        最右边呢个1对应的10进制 -> 2
······
lowbit(1) = 1
lowbit(2) = 2
lowbit(3) = 1
lowbit(4) = 4
lowbit(5) = 1
lowbit(6) = 2
······
lowbit(x) = (x) & (-x)

先感受一下这个lowbit有什么用：

$-x$ 代表 $x$ 的负数，计算机中负数使用对应的正数的补码来表示。

例如：

$x = 88_{(10)} = 1011000_{(2)} $

$-x = -88_{(10)} = (0100111_{(2)} + 1_{(2)}) = 101000_{(2)}$

$x \& (-x) = 1000_{(2)} = 8_{(10)}$

lowbit(x)代码实现：

inline int lowbit(int x)
{
    return x & -x;
}

• 那么C[]如何求得？

下面利用C[i]数组，求A数组中前i项的和

举个例子 $i=7$

sum[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]

C[4]=A[1]+A[2]+A[3]+A[4]; C[6]=A[5]+A[6]; C[7]=A[7];

可以推出: sum[7]=C[4]+C[6]+C[7];

序号写为二进制: sum[(111)]=C[(100)]+C[(110)]+C[(111)];

再举个例子 $i=5$

sum[5]=A[1]+A[2]+A[3]+A[4]+A[5]

C[4]=A[1]+A[2]+A[3]+A[4]; C[5]=A[5];

可以推出: sum[5]=C[4]+C[5];

序号写为二进制: sum[(101)]=C[(100)]+C[(101)];

C[1]=A[1];
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

结论： lowbit(x) 的值为纵轴，x轴为A数组下标。$C[i] = A[i-lowbit(i)+1] + … + A[i]$

后缀和更新代码：

inline void init()
{
    for(int i = 1;i <= n;++i)
    {
        int w;
        cin >> w;
        add(i,w);
    }
}

inline void add(int x,int w)
{
    for(int i = x;i <= n;i += lowbit(i))
        c[i] += w;
}

求区间 $0 — x$ 的和代码：

inline int getsum(int x)
{
    int ans = 0;
    for(int i = x;i > 0;i -= lowbit(i))
    {
        ans += C[i];
    }
    return 0;
}

例2：https://www.luogu.org/problemnew/show/P2068

代码：

#include<bits/stdc++.h>
using namespace std;

int C[1000100],N = 0,q = 0;

int lowbit(int x)
{
    return x & (-x);
}

void add(int x,int k)
{
    while(x<=N)
    {
        C[x]+=k;
        x+=lowbit(x);
    }
}

inline long long sum(int x)
{
    long long ans = 0;
    for(;x;x-=lowbit(x))
    {
        ans += C[x];
    }
    return ans;
}
int main(int argc, char const *argv[])
{
    cin >> N >> q;

    while(q--)
    {
        char qwq;
        cin >> qwq;
        if(qwq == 'x')
        {
            int x,y;
            cin >> x >> y;
            add(x,y);
        }
        if(qwq == 'y')
        {
            int x,y;
            cin >> x >> y;
            cout << sum(y) - sum(x-1) << endl;
        }
    }
    return 0;
}