树状数组

我不是女神ヾ 2023-08-17 16:26 102阅读 0赞

详细介绍：[https://www.cnblogs.com/xenny/p/9739600.html][https_www.cnblogs.com_xenny_p_9739600.html]

[http://www.sohu.com/a/245746824\_100201031][http_www.sohu.com_a_245746824_100201031]

**[https://www.cnblogs.com/wkfvawl/p/9445376.html][https_www.cnblogs.com_wkfvawl_p_9445376.html]**

## 单点更新、单点查询 ##

传统数组可做

**1.单点修改+区间查询**

int n;//点的数量
    int a[50005],c[50005]; //对应原数组和树状数组
    int lowbit(int x){
        return x&(-x);
    }
    void updata(int i,int k){    //在i位置加上k
        while(i <= n){
            c[i] += k;
            i += lowbit(i);
        }
    }
    //求sum(x)就是a[x]的前缀和，想查询l~r区间的元素和只需要求出来sum(r)-sum(l-1)
    int getsum(int i){
        int res = 0;
        while(i > 0){
            res += c[i];
            i -= lowbit(i);
        }
        return res;
    }
    int main()
    {

memset(a,0,sizeof(a));  
memset(c,0,sizeof(c));

模板题：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    //单点修改加区间查询
    using namespace std;
    int n;
    int a[50005],c[50005]; //对应原数组和树状数组
    int lowbit(int x){
        return x&(-x);
    }
    void updata(int i,int k){    //在i位置加上k
        while(i <= n){
            c[i] += k;
            i += lowbit(i);
        }
    }
    //求sum(x)就是a[x]的前缀和，想查询l~r区间的元素和只需要求出来sum(r)-sum(l-1)
    int getsum(int i){
        int res = 0;
        while(i > 0){
            res += c[i];
            i -= lowbit(i);
        }
        return res;
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        for(int i=1;i<=T;i++)
        {
            scanf("%d",&n);
            memset(a, 0, sizeof a);
            memset(c, 0, sizeof c);
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                updata(i,a[i]);
            }
            printf("Case %d:\n",i);
            char s[10];
            while(cin>>s){
            if(s[0]=='Q'){
         //区间查询
            int l,r;
            scanf("%d%d",&l,&r);
            cout<<getsum(r)-getsum(l-1)<<endl;
            }
            if(s[0]=='A'){
         //单点增加  第x个数加t
                int x,t;
                scanf("%d%d",&x,&t);
                updata(x,t);
            }
            if(s[0]=='S'){
         //单点减少  第x个数减t
                int x,t;
                scanf("%d%d",&x,&t);
                updata(x,-1*t);
            }
            if(s[0]=='E')//结束
                break;
            }
        }
    }

HDU - 1166

**2.区间修改+单点查询**

int n,m;
    int a[50005] = {
        0},c[50005]; //对应原数组和树状数组
    
    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){        //求D[1 - i]的和，即A[i]值
        int res = 0;
        while(i > 0){
            res += c[i];
            i -= lowbit(i);
        }
        return res;
    }
    
    int main(){
        cin>>n;

memset(a,0,sizeof(a));  
     memset(c,0,sizeof(c));

for(int i = 1; i <= n; i++){
            cin>>a[i];
            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
        
        //查询i位置的值
        int sum = getsum(i);
    
        return 0;
    }

例题：P3368 【模板】树状数组 2           https://www.luogu.org/problem/show?pid=3368

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cmath>
     4 #include<cstring>
     5 #include<algorithm>
     6 //单点修改加区间查询
     7 using namespace std;
     8 int n,m;
     9 int a[500005] = {
         0},c[500005]; //对应原数组和树状数组
    10 
    11 int lowbit(int x){
    12     return x&(-x);
    13 }
    14 
    15 void updata(int i,int k){    //在i位置加上k
    16     while(i <= n){
    17         c[i] += k;
    18         i += lowbit(i);
    19     }
    20 }
    21 
    22 int getsum(int i){        //求D[1 - i]的和，即A[i]值
    23     int res = 0;
    24     while(i > 0){
    25         res += c[i];
    26         i -= lowbit(i);
    27     }
    28     return res;
    29 }
    30 
    31 int main(){
    32     int m;
    33     cin>>n>>m;
    34     memset(a,0,sizeof(a));
    35     memset(c,0,sizeof(c));
    36     for(int i = 1; i <= n; i++){
    37     cin>>a[i];
    38     updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值
    39     }
    40     for(int i=1;i<=m;i++)
    41     {
    42         int t;
    43         cin>>t;
    44         if(t==1)
    45         {
    46             int x,y,k;
    47             cin>>x>>y>>k;
    48              //[x,y]区间内加上k
    49            updata(x,k);    //A[x] - A[x-1]增加k
    50            updata(y+1,-k);        //A[y+1] - A[y]减少k
    51         }
    52         else
    53         {
    54             int kk;
    55             cin>>kk;
    56             //查询i位置的值
    57            int sum = getsum(kk);
    58            cout<<sum<<endl;
    59         }
    60     }
    61     return 0;
    62 }

**3.区间修改+区间查询**

int n,m;
    int a[50005] = {
        0};
    int sum1[50005];    //(D[1] + D[2] + ... + D[n])
    int sum2[50005];    //(1*D[1] + 2*D[2] + ... + n*D[n])
    
    int lowbit(int x){
        return x&(-x);
    }
    
    void updata(int i,int k){
        int x = i;    //因为x不变，所以得先保存i值
        while(i <= n){
            sum1[i] += k;
            sum2[i] += k * (x-1);
            i += lowbit(i);
        }
    }
    
    int getsum(int i){        //求前缀和
        int res = 0, x = i;
        while(i > 0){
            res += x * sum1[i] - sum2[i];
            i -= lowbit(i);
        }
        return res;
    }
    
    int main(){
        cin>>n;
        for(int i = 1; i <= n; i++){
            cin>>a[i];
            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
    
        //求[x,y]区间和
        int sum = getsum(y) - getsum(x-1);
    
        return 0;
    }

例题：https://vjudge.net/problem/POJ-3468

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cmath>
     4 #include<cstring>
     5 #include<algorithm>
     6 //单点修改加区间查询
     7 using namespace std;
     8 #define ll long long
     9 int n,m;
    10 ll a[100005] = {
         0};
    11 ll sum1[100005];    //(D[1] + D[2] + ... + D[n])
    12 ll sum2[100005];    //(1*D[1] + 2*D[2] + ... + n*D[n])
    13 
    14 int lowbit(int x){
    15     return x&(-x);
    16 }
    17 
    18 void updata(int i,ll k){
    19     int x = i;    //因为x不变，所以得先保存i值
    20     while(i <= n){
    21         sum1[i] += k;
    22         sum2[i] += k * (x-1);
    23         i += lowbit(i);
    24     }
    25 }
    26 
    27 ll getsum(int i){        //求前缀和
    28     ll res = 0, x = i;
    29     while(i > 0){
    30         res += x * sum1[i] - sum2[i];
    31         i -= lowbit(i);
    32     }
    33     return res;
    34 }
    35 
    36 int main(){
    37     int Q;
    38     ios_base::sync_with_stdio(false);
    39 cin.tie(0);
    40 cout.tie(0);
    41     cin>>n>>Q;
    42     for(int i = 1; i <= n; i++){
    43         cin>>a[i];
    44         updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值
    45     }
    46 
    47     for(int i=1;i<=Q;i++)
    48     {
    49         char c;
    50         cin>>c;
    51         if(c=='Q')
    52         {
    53             int x,y;
    54             cin>>x>>y;
    55             long long sum = getsum(y) - getsum(x-1);
    56             cout<<sum<<endl;
    57         }
    58         else
    59         {
    60             int x,y;
    61             ll k;
    62             cin>>x>>y>>k;
    63              //[x,y]区间内加上k
    64             updata(x,k);    //A[x] - A[x-1]增加k
    65             updata(y+1,-k);        //A[y+1] - A[y]减少k
    66         }
    67     }
    68     return 0;
    69 }

转载于:https://www.cnblogs.com/Aiahtwo/p/11331107.html

[https_www.cnblogs.com_xenny_p_9739600.html]: https://www.cnblogs.com/xenny/p/9739600.html
[http_www.sohu.com_a_245746824_100201031]: http://www.sohu.com/a/245746824_100201031
[https_www.cnblogs.com_wkfvawl_p_9445376.html]: https://www.cnblogs.com/wkfvawl/p/9445376.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/8237ac6605064957810e4de1dc2659d1.png