数据结构 树状数组模板

树状数组

单点更新 区间查询

int a[maxn],c[maxn]; //原数组和树状数组

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

void updata(int i,int k) //第 i 个元素加 k
{  
    while(i <= n)
    {
        c[i] += k;
        i += lowbit(i);
    }
}
int getsum(int i) //前i个和
{    
    int res = 0;
    while(i > 0)
    {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

区间更新 单点查询

//利用原数组的差分数组建树
int a[maxn] = {0},c[maxn]; //原数组和树状数组

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

void updata(int i,int k)  //第 i 个元素加 k
{   
   while(i <= n)
   {
       
       c[i] += k;
       i += lowbit(i);
   }
}
 
int getsum(int i) //前i个
{
    int res = 0;
    while(i > 0)
    {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

/*
    updata(i,a[i] - a[i-1]);   //差分建树
    //[x,y]区间内加上k
    updata(x,k);         //A[x] - A[x-1]增加k
    updata(y+1,-k);      //A[y+1] - A[y]减少k
    //单点查询 差分建树所以单点查询变成了求和
    int sum = getsum(i);
*/

数据结构 树状数组模板

原文：https://www.cnblogs.com/hucorz/p/14346684.html