Article From:https://www.cnblogs.com/normaldisk/p/9126858.html

Line segment tree template — interval modification and summation

Title Description:
The number of numbers N and the number of operands Q:
For Q:
1 x y z Make interval [x, y] increase Z
2 x y Seek interval and

#include<cstdio>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
const int maxn=1e5+10;
int n, q;
LL a[maxn];
LL sum[maxn<<2], li[maxn<<2];

void _push_up(int rt) {
    sum[rt]=sum[rt<<1]+sum[(rt<<1)|1];
}//Update up, seek interval andVoid _setup (Int l, int r, int rt) {
    li[rt]=0;
    if(l==r){
        sum[rt]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    _setup(l, mid, rt<<1);
    _setup(mid+1, r, (rt<<1)|1);
    _push_up(rt);
}//Build a treeVoid _push_down (int RT, int m) {
    if(li[rt]) {
        li[rt<<1]+=li[rt];
        li[(rt<<1)|1]+=li[rt];
        sum[rt<<1]+=li[rt]*(m-(m>>1));
        sum[(rt<<1)|1]+=li[rt]*(m>>1);
        li[rt]=0;
    }
}//Update the Li tag down to the cellVoid _add (int x, int y, LL Z, Int l, int r) rt) {
    if(x<=l && y>=r) {
        li[rt]+=z;
        sum[rt]+=z*(r-l+1);
        return ;
    }
    _push_down(rt, r-l+1); //Edge update to save complexityInt mid= (l+r) > > 1;
    if(x<=mid) _add(x, y, z, l, mid, rt<<1);
    if(y>mid) _add(x, y, z, mid+1, r, (rt<<1)|1);
    _push_up(rt);
}

LL _query(int x, int y, int l, int r, int rt) {
    if(x<=l && y>=r) {
        return sum[rt];
    }
    _push_down(rt, r-l+1); //Update once again in summingInt mid= (l+r) > > 1;
    LL ans=0;
    if(x<=mid) ans+=_query(x, y, l, mid, rt<<1);
    if(y>mid) ans+=_query(x, y, mid+1, r, (rt<<1)|1); //'Clip 'intervalReturn ans;
}

int main() {
    scanf("%d%d", &n, &q);
    for(int i=1; i<=n; i++) {
        scanf("%lld", a+i);
    }
    _setup(1, n, 1);
    for(int i=0; i<q; i++) {
        int ls;
        scanf("%d", &ls);
        if(ls==1) {
            int x, y;
            LL z;
            scanf("%d%d%lld", &x, &y, &z);
            _add(x, y, z, 1, n, 1);
        } else if(ls==2) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%lld\n", _query(x, y, 1, n ,1));
        }
    }
    return 0;
}

There are many codes that use structure to implement line segment tree, but I am not used to using structure to implement it, because sometimes it is very hard to see a pile of points.

Link of this Article: Block tree

Leave a Reply

Your email address will not be published. Required fields are marked *