树状数组基本模板

树状数组可以很方便地实现数组的动态修改求和，并且代码量非常小！经过拓展之后，还可以实现区间修改单点查询、求区间最值和第 K 大值（继续学习之后再更新）

基本功能的实现主要有三个函数，lowbit 、 add 、 getsum；

单点加值区间求和：

#include<stdio.h>
#include<string.h>

const int maxn=1e5+5;        //数组大小

int c[maxn];

void init(){
    memset(c,0,sizeof(c));
}

inline int lowbit(int x){return x&(-x);}
//lowbit函数，决定下一个/上一个覆盖区间

void add(int x,int a,int n){
    for(int i=x;i<=n;i+=lowbit(i))c[i]+=a;
}
//单点加数

int sum(int x){
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))ans+=c[i];
    return ans;
}
//区间求和

  

动态单点更新并区间求最值功能：

#include<stdio.h>
#include<string.h>

const int maxn=1e5+5;        //数组大小
inline int lowbit(int x){return x&(-x);}
inline int max(int a,int b){return a>b?a:b;}
int a[maxn],ma[maxn];        //a为原数组，ma为最大值数组

void init(int n){
    for(int i=1;i<=n;i++){
        ma[i]=a[i];
        for(int j=1;j<lowbit(i);j<<=1)
            ma[i]=max(ma[i],ma[i-j]);
    }
}
//init函数是构建最大值数组的函数，其中 n 是数组长度，a 是原数组，ma 是区间最大值数组，表示 [ i - lowbit [ i ]  ,i ]区间内的最大值，对于每一个 i ，用被其覆盖的各个区间的最大值更新它。

void change(int ind,int v,int n){
    a[ind]=v;
    for(int i=ind;i<=n;i+=lowbit(i)){
        ma[i]=v;
        for(int j=1;j<lowbit(i);j<<=1)
            ma[i]=max(ma[i],ma[i-j]);
    }
}
//将第ind个数更新为v

int query(int l,int r){
    int ans=a[r];
    while(1){
        ans=max(ans,a[r]);
        if(l==r)break;
        for(r-=1;r-l>=lowbit(r);r-=lowbit(r))
            ans=max(ans,ma[r]);
    }
    return ans;
}
//查询 [ l , r ] 区间内的最大值，通过不断考虑 r 覆盖的区间中的最大值，将 r 不断左移直到等于 l ，返回这中间的最大值，对于每一次遍历的 r ，若 r 覆盖的区间在查询区间内，就直接使用该区间的最大值，然后左移 r 值原先 r 覆盖的区间左，若 r 覆盖的区间比查询区间大，就直接考虑 r 的值，然后将 r 左移至 k - 1 ；这样循环直到 l == r 。

树状数组还有区间加值单点查询的功能：

#include<stdio.h>
#include<string.h>

const int maxn=1e5+5;        //数组大小

int c[maxn];

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

void change(int x,int v,int n){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}

int sum(int x){                        //求x单点值
    int s=0;
    while(x){
        s+=c[x];
        x-=lowbit(x);
    }
    return s;
}

void update(int l,int r,int v){        //将区间[l,r]加v
    change(l,v);
    change(r+1,-v);
}