线段树算法

线段树

参考文章：

https://blog.csdn.net/zearot/article/details/48299459

递归实现

#include<iostream>
using namespace std;
typedef long long LL;
const int MAXN = 50010;
LL a[MAXN], ans[MAXN << 2], lazy[MAXN << 2];
void PushUp(LL rt)
{
    ans[rt] = ans[rt << 1] + ans[rt << 1 | 1];
}
void Build(LL l, LL r, LL rt)
{
    if (l == r)
    {
        ans[rt] = a[l];
        return;
    }
    LL mid = (l + r) >> 1;
    Build(l, mid, rt << 1);
    Build(mid + 1, r, rt << 1 | 1);
    PushUp(rt);
}
void PushDown(LL rt, LL ln, LL rn)//ln表示左子树元素结点个数，rn表示右子树结点个数
{
    if (lazy[rt])
    {
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        ans[rt << 1] += lazy[rt] * ln;
        ans[rt << 1 | 1] += lazy[rt] * rn;
        lazy[rt] = 0;
    }
}
void Update(LL L, LL R, LL C, LL l, LL r, LL rt)
{
    if (L <= l&&r <= R)
    {
        ans[rt] += C*(r - l + 1);
        lazy[rt] += C;
        return;
    }
    LL mid = (l + r) >> 1;
    PushDown(rt, mid - l + 1, r - mid);
    if (L <= mid) Update(L, R, C, l, mid, rt << 1);
    if (R > mid) Update(L, R, C, mid + 1, r, rt << 1 | 1);
    PushUp(rt);
}
LL Query(LL L, LL R, LL l, LL r, LL rt)
{
    if (L <= l&&r <= R)
        return ans[rt];
    LL mid = (l + r) >> 1;
    PushDown(rt, mid - l + 1, r - mid);//若更新只有点更新，不需要这句
    LL ANS = 0;
    if (L <= mid) ANS += Query(L, R, l, mid, rt << 1);
    if (R > mid) ANS += Query(L, R, mid + 1, r, rt << 1 | 1);
    return ANS;
}
int main()
{
    LL n, m, t;
    LL op, u, v, d, l, r;
    cin >> n >> m;
    for (LL i = 1; i <= n; i++){
        cin >> t;
        a[i] = t;
    }
    Build(1, n, 1);
    for (LL i = 0; i < m; i++){
        cin >> op;
        if (op == 1){
            cin >> u >> v >> d;
            Update(u, v, d, 1, n, 1);
        }
        else if (op == 2){
            cin >> l >> r;
            //区间查询 
            LL ANS = Query(l, r, 1, n, 1);
            cout << ANS % 1000000007 << endl;
        }
    }
    return 0;
}