To the moon HDU - 4348 | 主席树套线段树（区间修改区间求和）

主席树套线段数模板

题意：

分析：
-由于主席树的节点是公用的，所以在update的时候不能用传统的pushdown（会破坏之前的历史状态）；又因为不能pushdown，所以update时候就不能pushup了，因为下面的数据不准。
-query的时候遇到懒惰标记就加上
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
struct node
{
    int lson, rson;
    ll sum, add;
}t[maxn << 5];
int root[maxn], v[maxn];
int tot;
int tim;
int n, m;

void init()
{
    tot = 0;
    tim = 0;
}

int build(int l, int r)
{
    int tar = tot++;
    t[tar].add = 0;
    if(l == r) t[tar].sum = v[l];
    else
    {
        int mid = l + r >> 1;
        t[tar].lson = build(l, mid), t[tar].rson = build(mid + 1, r);
        t[tar].sum = t[t[tar].lson].sum + t[t[tar].rson].sum;
    }
    return tar;
}

int update(int pre, int ll, int rr, int val, int l, int r)
{
    int tar = tot++;
    t[tar] = t[pre];
    t[tar].sum += (min(rr, r) - max(ll, l) + 1) * val;
    if(ll <= l && r <= rr) t[tar].add += val;
    else
    {
        int mid = l + r >> 1;
        if(ll <= mid) t[tar].lson = update(t[pre].lson, ll, rr, val, l, mid);
        if(rr > mid) t[tar].rson = update(t[pre].rson, ll, rr, val, mid + 1, r);
    }
    return tar;
}

ll query(int tar, int li, int ri, int l, int r)
{
    if(li <= l && r <= ri) return t[tar].sum;
    int mid = l + r >> 1;
    ll res = (min(ri, r) - max(li, l) + 1) * t[tar].add;
    if(li <= mid) res += query(t[tar].lson, li, ri, l, mid);
    if(ri > mid) res += query(t[tar].rson, li, ri, mid + 1, r);
    return res;
}

int main()
{
    close();
   while(cin >> n >> m)
   {
        init();
        for(int i = 1; i <= n; i++) cin >> v[i];
        root[0] = build(1, n);
        while(m--)
        {
            char ope[3];
            int l, r, v;
            cin >> ope;
            if(ope[0] == 'C')
            {
                cin >> l >> r >> v;
                tim++;
                root[tim] = update(root[tim - 1], l, r, v, 1, n);
            }
            else if(ope[0] == 'Q')
            {
                cin >> l >> r;
                cout << query(root[tim], l, r, 1, n) << endl;
            }
            else if(ope[0] == 'H')
            {
                cin >> l >> r >> v;
                cout << query(root[v], l , r, 1, n) << endl;
            }
            else cin >> v, tim = v;
        }
   }
}