Luogu P3368: 【模板】树状数组 2

题目

题目链接在这里

这个题目的名字虽然叫树状数组，但是我用线段树做的哈哈。线段树虽然没有树状数组快，但是能处理的问题相对来说更多；就像分块比线段树能解决的问题更多一样，越暴力的算法能解决的问题也越多。这个和我之前写的几个还是换汤不换药。

吐槽

这个csdn是什么毛病了, 文章字少就代表质量不高吗？解释性的东西放在代码里不行吗，我写个文章还提示我质量低得不到流量推广，真就把自己平台这点流量看的这么香。

代码

#include <cstdio>
#include <algorithm>

using namespace std;
#define lc k<<1
#define rc k<<1|1

typedef long long ll;
const int maxn = 5e6+5;
ll a[maxn], f[maxn<<2], v[maxn<<2];

inline void build_tree(int k, int l, int r) {
    
    v[k] = 0;
    if (l == r) {
     f[k] = a[l]; return; }
    int m = (l+r) >> 1;
    build_tree(lc, l, m);
    build_tree(rc, m+1, r);
    f[k] = f[lc] + f[rc];
}

inline void push_down(int k, int l, int r) {
    
    if(v[k]) {
    
        int m = (l+r) >> 1;
        f[lc] += (m-l+1)*v[k];
        v[lc] += v[k];

        f[rc] += (r-m)*v[k];
        v[rc] += v[k];
        v[k] = 0;
    }
}

inline void update(int k, int l, int r, int x, int y, int z) {
    
    push_down(k, l, r);
    if(l == x && r == y) {
     v[k] = z; f[k] += (r-l+1)*z; return; }
    int m = (l+r) >> 1;
    if(y <= m) {
    
        update(lc, l, m, x, y, z);
    } else if(x > m) {
    
        update(rc, m+1, r, x, y, z);
    } else {
    
        update(lc, l, m, x, m, z);
        update(rc, m+1, r, m+1, y, z);
    }
    f[k] = f[lc] + f[rc];
}

inline ll query(int k,int l, int r, int x, int y) {
    
    push_down(k, l, r);
    if(l == x && r == y) return f[k];
    int m = (l+r) >> 1;
    ll ans;
    if(y <= m) {
    
        ans = query(lc, l, m, x, y);
    } else if(x > m) {
    
        ans = query(rc, m+1, r, x, y);
    } else {
    
        ans =  query(lc, l, m, x, m) + query(rc, m+1, r, m+1, y);
    }
    f[k] = f[lc] + f[rc];
    return ans;
}

int main(void)
{
    
    freopen("in.txt", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
    
        scanf("%lld", &a[i]);
    }
    build_tree(1, 1, n);
    int op, x, y;
    ll k;
    while(m--) {
    
        scanf("%d", &op);
        if(op == 1) {
    
            scanf("%d%d%lld", &x, &y, &k);
            update(1, 1, n, x, y, k);
        } else {
    
            scanf("%d", &x);
            printf("%lld\n", query(1, 1, n, x, x));
        }
    }
    return 0;
}