树状数组

树状数组，是一个用于在近似 $O(logn)$ 时间内动态修改以及查询前缀和的数据结构，以下我们先来看以下树关系表格

这里表达的是，16的子节点有8, 12, 14, 15

8的子节点有4, 6, 7

12的子节点有10, 11，即夹在12与它的同级节点8之间

我们把数值与它的二进制一起形象化画出下图

graph TD;
2,0010-->1,0001
4,0100-->3,0011
4,0100-->2,0010
6,0110-->5,0101
8,1000-->7,0111
8,1000-->6,0110
8,1000-->4,0100
10,1010-->9,1001
12,1100-->11,1011
12,1100-->10,1010
14,1110-->13,1101
16,10000-->8,1000
16,10000-->12,1100
16,10000-->14,1110
16,10000-->15,1111

这样构造的原理是运用到一个二进制运算技巧，假设一个节点x，那么它的父节点就是x + (x & -x)，其中，x & -x是去掉右起第一个1的左边的1，例如x如果是6，二进制是110，只保留最右边的1结果就是10了，所以6的父节点就是6+2=8，更多的可以参考这篇二进制技巧。

前缀和

给一个数组a，如果我们需要计算前n个元素的和 $\sum_{i=1}^n{a[i]}$ ，直接累加是很慢的，这里我们用树状数组，我们规定，每个节点保存的值，是它和它的子节点的和，我们用数组 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 6, 5, 4, 3, 2, 1 画个表格，注意数组下标从1开始。

那有了这个表，我们要是求出前4个数的和，直接看第4列是30，答案就出来了，因为它上面的数就是它和它所有子结点的和。但如果是别的数呢，例如要求前7个数的和，就不能光看第7列了，需要把第4列、第6列和第7列的3个数相加，即30+9+3=42就是前7个数的和。注意到这三列其实就是三个同级节点，而且我们通过7这个数本身可以轻松计算前两列的数，计算的方法是x - (x & -x)，把x=7代入，得到6，再把6代入，得到4，再把4代入，得到0，0就结束了，而在这个迭代的过程里，就知道我们应该把4,6,7三列的数相加。

再换一个数，例如11呢，把x=11代入，得到10，再把10代入，得到8，再把8代入，得到0，所以我们应该把8,10,11三列的数加起来，即44+1+6=51就是前11个数的和。

把以上过程写成函数，就是

int sum(int fwtree[], int x)
{
    int r = 0;
    while (x > 0)
    {
        r += fwtree[x];
        x -= x&-x;
    }
    return r;
}

可以看出，这段代码的时间复杂度近似是 $O(logx)$

动态维护

还是前面的数组 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 6, 5, 4, 3, 2, 1 ，现在假如已经计算好了树状数组，但我们需要对第6个元素，让它减少6，怎么操作呢，其实很简单，根据定义，在子节点修改的时候，让它的所有父节点都做相同的修改，那么6的父节点分别有8,16，所以我们对第6,8,16列都一起减少6，得到以下新表格

这样就维护完成了，所以咱们的实现代码也非常的简单

void add(int fwtree[], int treesize, int x, int add)
{
    while (x <= treesize)
    {
        fwtree[x] += add;
        x += x&-x;
    }
}

区间和

我们之所以需要前缀和，就是为了能快速求区间和。例如我们需要求出数组第i个到第j个元素的和，那么我们用sum(x)表示前x个元素的和，那么可以转化为求sum(j) - sum(i-1)

区间操作+单点查询

因为树状数组的修改是单点修改，即每次只能修改一个数，那么现在我们提出一个新问题，如果我们需要多次做区间操作（整个区间的数同时加上y），然后查询数组里面指定第k个元素是什么，例如这个题loj131

由于树状数组不能快速做区间操作，我们用到另一个技巧叫做差分法，我们对数组 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 6, 5, 4, 3, 2, 1求相邻元素的差，得到新的数组

9, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6, -1, -1, -1, -1, -1

这样做了后，如果我们要求出原来第k个元素，那么就是求前k个元素之和，所以如果第i个元素加上a，那么相当于i后面所有元素都加上a。

所以，这时候的区间操作，就会变成单点操作，例如我们要对区间[i,j]所有的元素加上a，那么在差分了以后，其实就是对第i个元素加上a，再对第j+1个元素减去a。

区间操作+区间和

如果我们既要做区间操作，同时还要求区间和怎么办，为了支持区间操作，我们仍然先做差分，然后接下来就是让人头痛的数学推导，假设数组a是原数组，b是a的差分数组，由前缀和的定义，我们求前n个元素的和，即

$$ \sum_{i=1}^{n} a_i $$

展开为b数组表达

$$ = \sum_{i=1}^n{} \sum_{j=1}^i b_j $$

展开，合并同类项

$$ = \sum_{i=1}^n b_i\times(n-i+1) $$

$$ = (n+1)\times\sum_{i=1}^n b_i - \sum_{i=1}^n b_i\times i $$

那么，我们再定义一个c数组，满足c[i] == b[i] * i，然后我们再分别对b和c维护一个树状数组，定义sum(b,x)表示数组b前x个元素的和，sum(c,x)表示数组c前x个元素的和，那么我们便可以通过计算(x + 1) * sum(b, x) - sum(c, x)求出数组a的前缀和。

习题：loj132

拓展

树状数组还有一些别的技巧，一是 $O(n)$ 建立，通过已知数组a在 $O(n)$ 时间生成对应的树状数组（直接add来操作是nlogn），这个在这里不做介绍。

还有权值树状数组求第k小元素。所谓权值树状数组，就是用a[i] = v来表示数值i重复出现了v次，所以v是非负数，那么这个数组的前缀和就是递增的，即存在二分。然后对数组a维护的树状数组直接二分的话是 $O(lognlogn)$ ，但我们可以运用树状数组的特性优化到 $O(logn)$ ，以下是实现代码

int kth(int fwtree[], int size, int k)
{
    int cnt = 0, ret = 0;
    for (int i = (int)(log(size + 0.1) / log(2)); ~i; --i)
    {
        ret += 1 << i;
        if (ret >= size || cnt + fwtree[ret] >= k)
            ret -= 1 << i;
        else
            cnt += fwtree[ret];
    }
    return ret + 1;
}

权值树状数组还有一个应用，就是用来求逆序数，先对原数组排序求出每个元素的rank，转化为长度n，元素为1~n的一个排列，之后使用权值树状数组，就可以轻松求出在a[1]到a[i-1]有多少个元素比a[i]要大，计算sum(n) - sum(a[i])便知，把结果累加就是逆序数。

模板

区间修改+区间求和模板

#include <vector>
typedef long long ll;


struct fwtree_range
{
    std::vector<int> ta;
    std::vector<ll> tb;
    int sz;
    void init(int size)
    {
        ta.clear(); ta.resize(size + 1);
        tb.clear(); tb.resize(size + 1);
        sz = size;
    }
    void add(int x, int a)
    {
        ll v = a * (ll)x;
        for (; x <= sz; x += x&-x)
        {
            ta[x] += a;
            tb[x] += v;
        }
    }
    template <class T>
    ll sum_t(T& t, int x)
    {
        ll r = 0;
        for (; x > 0; x -= x&-x)
            r += t[x];
        return r;
    }
    ll sum(int x)
    {
        return (x + 1) * sum_t(ta, x) - sum_t(tb, x);
    }
    void range_add(int l, int r, int a)
    {
        add(l, a);
        add(r + 1, -a);
    }
    ll range_sum(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
};

用法，调用init初始化大小后，使用range_add及range_sum做区间修改及区间和查询就行了，当然它也支持单点修改和单点查询，你令区间l == r就行了。