zkw 线段树

存一份模板代码（区间修改、区间查询）：
/* zkw Segment Tree

 * Au: GG

 */

#include <cstdio>

typedef long long ll;

const int N=1e5+3;

int n, m, zkw; ll t[N<<2], laz[N<<2];

inline void update(int x, int y, ll val) {

    ll l=0, r=0, f=1;

    for (x+=zkw-1, y+=zkw+1; x^y^1; x>>=1, y>>=1, f<<=1) {

        t[x]+=val*l, t[y]+=val*r;

        if (~x&1) laz[x^1]+=val, t[x^1]+=val*f, l+=f;

        if (y&1) laz[y^1]+=val, t[y^1]+=val*f, r+=f;

    }

    for (; x; x>>=1, y>>=1) t[x]+=val*l, t[y]+=val*r;

}

inline ll query(int x, int y) {

    ll res=0, l=0, r=0, f=1;

    for (x+=zkw-1, y+=zkw+1; x^y^1; x>>=1, y>>=1, f<<=1) {

        if (laz[x]) res+=laz[x]*l;

        if (laz[y]) res+=laz[y]*r;

        if (~x&1) res+=t[x^1], l+=f;

        if (y&1) res+=t[y^1], r+=f;

    }

    for (; x; x>>=1, y>>=1) res+=laz[x]*l, res+=laz[y]*r;

    return res;

}

int main() {

    scanf("%d%d", &n, &m);

    for (zkw=1; zkw<=n+1; zkw<<=1);

    for (int i=zkw+1; i<=zkw+n; i++) scanf("%lld", t+i);

    for (int i=zkw-1; i>0; --i) t[i]=t[i<<1]+t[i<<1|1];

    while (m--) {

        int opt, a, b; ll c; scanf("%d%d%d", &opt, &a, &b);

        if (opt<2) scanf("%lld", &c), update(a, b, c);

        else printf("%lld\n", query(a, b));

    }

    return 0;

}
巴特西

zkw 线段树

最新文章

热门文章
