树状数组

为了方便查看，本文转自维基百科：https://zh.wikipedia.org/wiki/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84

维基百科（中文）上对树状数组的介绍基本就是一个说明书性质的，并没有证明推导啥的，等着以后上课无聊时在看看证明推导吧，挖坑。
树状数组现多用于高效计算数列的前缀和， 区间和。它可以以的时间得到任意前缀和，并同时支持在时间内支持动态单点值的修改。空间复杂度。。

结构起源

按照Peter M. Fenwick的说法，正如所有的整数都可以表示成2的幂和，我们也可以把一串序列表示成一系列子序列的和。采用这个想法，我们可将一个前缀和划分成多个子序列的和，而划分的方法与数的2的幂和具有极其相似的方式。一方面，子序列的个数是其二进制表示中1的个数，另一方面，子序列代表的f[i]的个数也是2的幂。

预备函数

定义一个Lowbit函数，返回参数转为二进制后,最后一个1的位置所代表的数值.

例如,Lowbit(34)的返回值将是2；而Lowbit(12)返回4；Lowbit(8)返回8。

将34转为二进制,为0010 0010,这里的”最后一个1″指的是从位往前数,见到的第一个1,也就是位上的1.

程序上，((Not I)+1) And I表明了最后一位1的值,

仍然以34为例,Not 0010 0010的结果是 1101 1101(221),加一后为 1101 1110(222), 把 0010 0010与1101 1110作AND,得0000 0010(2).

Lowbit的一个简便求法:（C++）

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

新建

定义一个数组 BIT，用以维护的前缀和，则:

具体能用以下方式实现：（C++）

void build()
{ 
    for (int i = 1; i <= MAX_N; i++)
    {
        BIT[i] = A[i - 1];
        for (int j = i - 2; j >= i - lowbit(i); j--)
            BIT[i] += A[j];
    }
}
//注：这里的求和将汇集到非终端结点（D00形式）
//BIT中仅非终端结点i值是 第0~i元素的和
//终端结点位置的元素和，将在求和函数中求得
//BIT中的index，比原数组中大1

修改

假设现在要将的值增加delta,

那么,需要将覆盖的区间包含的值都加上delta.

这个过程可以写成递归,或者普通的循环.

需要计算的次数与数据规模N的二进制位数有关,即这部分的时间复杂度是O(LogN)

修改函数的C++写法

void edit(int i, int delta)
{
    for (int j = i; j <= MAX_N; j += lowbit(j))
        BIT[j] += delta;
}

求和

假设我们需要计算的值.

1. 首先,将ans初始化为0，将i初始化为k.
2. 将ans的值加上BIT[i]
3. 将i的值减去lowbit(i)
4. 重复步骤2～3，直到i的值变为0

求和函数的C/C++写法

int sum (int k)
{
    int ans = 0;
    for (int i = k; i > 0; i -= lowbit(i))
        ans += BIT[i];
    return ans;
}

复杂度

初始化复杂度最优为

单次询问复杂度,其中N为数组大小

单次修改复杂度,其中N为数组大小

空间复杂度

例题

未完待续…………

例题 1. P3374 【模板】树状数组 1

题目链接：https://www.luogu.org/problemnew/show/P3374
真*模板题，没啥好说的
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a[500050],bit[500050];
int n,m;

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

void updata(int id,int data)
{
    for(int i=id;i<=n;i+=low_bit(i))
    {
        bit[i]+=data;
    }
}

int query(int k)
{
    int ans=0;
    for(int i=k;i>0;i-=low_bit(i))
    {
        ans+=bit[i];
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        bit[i]=a[i-1];
        for(int j=i-2;j>=i-low_bit(i);j--)
        {
            bit[i]+=a[j];
        }
    }
    int d,x,y;
    while(m--)
    {
        cin>>d>>x>>y;
        if(d==1)
        {
            updata(x,y);
        }
        else if(d==2)
        {
            cout<<query(y)-query(x-1)<<endl;
        }
    }
    return 0;
}