简单的线段树模板(区间修改和查询)

简单的线段树模板(区间修改和查询)

2019年11月6日 1 作者 Ender

花了很久复习了下线段树,两个查询条件写错一直RE找了一个小时,很难受

#include <iostream>
#include <cstdio>
#include <algorithm>
const long long MAXN = 1e5 + 233;
struct node{
    long long left, right, value, tag;
}tree[MAXN * 4];
long long origin[MAXN];
long long n, m, ans;
inline long long leftSon(long long fa) {
    return fa << 1;
}
inline long long rightSon(long long fa) {
    return (fa << 1) + 1;
}
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
void build(long long index, long long l, long long r) {
    tree[index].left = l;
    tree[index].right = r;
    if (l == r) {
        tree[index].value = origin[l];
        return;
    }
    long long mid = (l + r) / 2;
    build(leftSon(index), l, mid);
    build(rightSon(index), mid + 1, r);
    tree[index].value = tree[leftSon(index)].value + tree[rightSon(index)].value;
}
inline void dropTag(long long index) {
    if (tree[index].tag) {
        tree[leftSon(index)].value += tree[index].tag * (tree[leftSon(index)].right - tree[leftSon(index)].left + 1);
        tree[rightSon(index)].value += tree[index].tag * (tree[rightSon(index)].right - tree[rightSon(index)].left + 1);
        tree[leftSon(index)].tag += tree[index].tag;
        tree[rightSon(index)].tag += tree[index].tag;
        tree[index].tag = 0;
    }
}
inline void plus(long long index, long long l, long long r, long long k) {
    if (l <= tree[index].left && r >= tree[index].right) {
        tree[index].value += k * (tree[index].right - tree[index].left + 1);
        tree[index].tag += k;
        return;
    }
    dropTag(index);
    long long mid = (tree[index].left + tree[index].right) / 2;
    if (l <= mid) plus(leftSon(index), l, r, k);
    if (r > mid) plus(rightSon(index), l, r, k);
    tree[index].value = tree[leftSon(index)].value + tree[rightSon(index)].value;
}
inline void search(long long index, long long l, long long r) {
    if (l <= tree[index].left && r >= tree[index].right) {
        ans += tree[index].value;
        return;
    }
    dropTag(index);
    long long mid = tree[index].left + tree[index].right >> 1;
    if (l <= mid) search(leftSon(index), l, r);
    if (r > mid) search(rightSon(index), l, r);
}
int  main() {
    register int x, y, z, k;
    n = read(), m = read();
    for(int i = 1; i <= n; i++) origin[i] = read();
    build(1,1,n);
    for(long long i = 1; i <= m; ++i) {
        z = read();
        if(z == 1) {
            x = read(), y = read(), k = read();
            plus(1, x, y, k);
        }
        if(z == 2) {
            x = read(), y = read(), ans = 0;
            search(1, x, y);
            std::cout << ans << std::endl;
        }
    }
    return 0;
}