树状数组：单点修改区间查询

树状数组： 每个节点储存所有子节点和该节点对应的值之和，每个节点的值的求解有一个lowbit()函数的关系。

复杂度： 更新单点信息O(logn)，求区间和O(logn).

树状数组能解决的，线段树基本都能解决。线段树

参考：树状数组详解 , 树状数组详解2

核心函数：

ll A[600005],n;
//A数组存的是所有子节点加上自身的和,不同实现可以有不同含义

ll lowbit(ll X){return X&(-X);}

void update(ll I,ll K){    //在i位置加上k
    while(I <= n){
        A[I] += K;
        I += lowbit(I);
    }
}

ll getsum(ll I){        //求1 - i的和
    ll res = 0;
    while(I > 0){
        res += A[I];
        I -= lowbit(I);
    }
    return res;
}

单点修改，区间查询：

int main()
{
    cin>>n>>w;
    for(ll i=1;i<=n;i++){
        ll tmp;cin>>tmp;
        update(i,tmp);//初始赋值
    }
    char op;
    ll x,y;
    for(ll i=1;i<=w;i++){
        cin>>op>>x>>y;
        if(op=='1'){
            update(x,y);//在x位置加上y
        }
        else{
        	//求区间[x,y]的所有数之和
            ll tot1=getsum(x-1),tot2=getsum(y);
            cout<<tot2-tot1<<"\n";
        }
    }

    return 0;
}

区间修改，单点查询：

看到区间修改单点查询，很容易想到差分数组（O(1) 时间修改区间，但O(n) 时间查询单点）。差分数组的查询比较慢，当问题的查询比较多时，可以用树状数组优化（因为树状数组更新单点和查询区间都是logn的）。

int main()
{
    cin>>n>>w;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        update(i,a[i]-a[i-1]);//用A[]存差分数组信息
    }
    char op;
    ll x,y,k;
    for(ll i=1;i<=w;i++){
        cin>>op;
        if(op=='1'){
            cin>>x>>y>>k;
            update(x,k);
            update(y+1,-k);
        }
        else{
            cin>>x;
            ll ans=getsum(x);
            cout<<ans<<"\n";
        }
    }

    return 0;
}

区间修改，区间查询：

这个功能和线段树比较重复了，只是树状数组的常数时间更小一些，树状数组更好编写一些。
例题：A Simple Problem with Integers

//和之前的不一样,现在存两个数组
ll sum1[500005];    //(D[1] + D[2] + ... + D[n])
ll sum2[500005];    //(1*D[1] + 2*D[2] + ... + n*D[n])

ll lowbit(ll X){
    return X&(-X);
}

void update(ll I,ll K){
    ll x = I;    //因为x不变，所以得先保存i值
    while(I <= n){
        sum1[I] += K;
        sum2[I] += K * (x-1);
        I += lowbit(I);
    }
}

ll getsum(ll I){        //求前缀和
    ll res = 0, x = I;
    while(I > 0){
        res += x * sum1[I] - sum2[I];
        I -= lowbit(I);
    }
    return res;
}

int main()
{
    cin>>n>>w;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        update(i,a[i]-a[i-1]);//类似前面差分数组
    }
    char op;
    ll x,y,k;
    for(ll i=1;i<=w;i++){
        cin>>op;
        if(op=='C'){
            cin>>x>>y>>k;
            update(x,k);
            update(y+1,-k);
        }
        else{
            cin>>x>>y;
            ll ans=getsum(y)-getsum(x-1);//区间查询
            cout<<ans<<"\n";
        }
    }

    return 0;
}