模板（线段树 + 树状数组 + 区间修改 + 区间查询）eg：POJ 3468 - A Simple Problem with Integers

太过爱你忘了你带给我的痛 2022-06-07 04:35 157阅读 0赞

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    #define lson l, m, rt<<1//左移运算符，这里称这个为左儿子
    #define rson m+1, r, rt<<1|1//右儿子
    
    using namespace std;  
    
    typedef long long ll;  
    const int maxn = 100000 + 10;  
    ll sum[maxn<<2];  //存放节点
    ll make[maxn<<2];  //懒惰标记
                        //懒惰标记其实是在节点处标记一下，下面的数字需要的操作，先不做处理，等全部操作标记后一次性更新
    
    void pushUP(int rt) {  //想上更新
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    }
    
    void pushDown(int rt, int len) {  //延迟标记向下更新 
        if(make[rt]) {
       //如果标记存在就需要更新
            make[rt<<1] += make[rt];//更新左儿子，的懒惰标记
            make[rt<<1|1] += make[rt];
            sum[rt<<1] += make[rt]*(len-(len>>1));//节点更新
            sum[rt<<1|1] += make[rt]*(len>>1);
            make[rt] = 0;//把标记去掉
        }
    }
    
    void build(int l, int r, int rt) {  
        if(l == r) {
       //如果左边=右边边界，说明这个已经是一个点了，比如[1,1]闭区间里只有1个数
            scanf("%lld", &sum[rt]);//然后更细端点值，我们这里称他为叶子
            return;
        }
        int m = (r+l)>>1;
        build(lson);//如果没有到叶子的话，继续往下分，这里称为左儿子
        build(rson);//右儿子
        pushUP(rt);//吧叶子更新后，上面的节点并没有更新，向上更新
    }
    
    void updata(int L, int R, ll c, int l, int r, int rt) {  
        if(L<=l && r<=R) {
            make[rt] += c;//这里多更新了懒惰标记，不需要更新下面节点的值，最后一次更新
            sum[rt] += c*(r-l+1);//在原数基础上加减的话用+=(全部用+=，需要减的话传入的时候变为负的）
                                //更改原数的话，用=
            return; 
        }
        pushDown(rt, r-l+1);//全部值录入之后向下更新
        int m = (r+l)>>1;
        if(m >= L) updata(L, R, c, lson);//更新左儿子
        if(m < R) updata(L, R, c, rson);//右儿子
        pushUP(rt); 
    }
    
    ll query(int L, int R, int l, int r, int rt) {  
        if(l>=L && R>=r) {
            return sum[rt];//返回
        }
        pushDown(rt, r-l+1);如果这个借点不够用，就需要向下更新
        int m = (r+l)>>1;
        ll ret = 0;
        if(L <= m) ret += query(L, R, lson);
        if(R > m) ret += query(L, R, rson);
        return ret;
    }
    
    int main() {
        int n, q;
        scanf("%d %d", &n, &q);
        memset(sum, 0, sizeof(sum));
        memset(make, 0, sizeof(make));
        build(1, n, 1);
        for(int i = 0; i < q; i++) {
            char op;
            int a, b;
            ll c;
            cin >> op;
            if(op == 'C') {
                scanf("%d %d %lld", &a, &b, &c);
                updata(a, b, c, 1, n, 1);//更新
            }else {
                scanf("%d %d", &a, &b);
                printf("%lld\n", query(a, b, 1, n, 1));//查询
            }
        }
        return 0;
    }

树状数组 [解释][Link 1]  
这个自己退出了公式，然后根据公式维护两个数组，用运算算出区间值  
函数都很简单，更新的东西不太一样，因为是根据公式来算的，没有实际意义（难以理解）

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    
    using namespace std;
    
    typedef long long ll;
    const int MAX = 100000 + 10;  
    ll n, q;  
    ll sum[MAX], c1[MAX], c2[MAX];
    
    ll lowbit(ll x) {  
        return x&(-x);
    }
    
    void Update(ll x, ll d, ll *c) {  
        while(x <= n) {
            c[x] += d;
            x += lowbit(x);
        }
    }
    
    ll Query(ll x, ll *c){  
        ll sum = 0;
        while(x > 0) {
            sum += c[x];
            x -= lowbit(x);
        }
        return sum;
    }
    
    int main(){  
        char op[3];
        ll x, y, d;
        while(~scanf("%lld %lld", &n, &q)) {
            memset(c1, 0, sizeof c1);
            memset(c2, 0, sizeof c2);
            for(int i = 1; i <= n; i++) {
                scanf("%lld", sum+i);
                sum[i] += sum[i-1];
            }
            for(int i = 0; i < q; i++) {
                scanf("%s", op);
                if(op[0] == 'C'){
       //ans[x]+=d,ans[y+1]-=d
                    scanf("%lld %lld %lld", &x, &y, &d);
                    Update(x, d, c1);//为什么这样维护，更新，去看[解释]
                                //http://blog.csdn.net/xiao_bai_9527/article/details/73612579
                    Update(y+1, -d, c1);
                    Update(x, x*d, c2);
                    Update(y+1, -(y+1)*d, c2);
                }else {
                    scanf("%lld %lld", &x, &y);
                    printf("%lld\n",sum[y]-sum[x-1]+Query(y,c1)*(y+1)-Query(x-1,c1)*x-Query(y,c2)+Query(x-1,c2));
                }
            }
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/xiao_bai_9527/article/details/73612579