To the moon

区间更新

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 1e5 + 5;
struct TREE {
  int l,r;
  ll val,lazy;
} tr[MAX*40];

int tot;
int a[MAX];
int root[MAX];
void pushup(int cur,int l,int r) {            //更新父节点
  tr[cur].val = tr[tr[cur].l].val + tr[tr[cur].r].val + tr[cur].lazy*(r-l+1);    //左节点+右节点+懒标记
}
int build(int l,int r) {
  int cur = ++tot;
  tr[cur].lazy = 0;
  if(l == r) {
    tr[cur].val = a[l];                      //这一步好像没啥用？
    return cur;
  }
  int m = (l+r)>>1;
  tr[cur].l = build(l,m);
  tr[cur].r = build(m+1,r);
  pushup(cur,l,r);
  return cur;
}
int update(int pre,int pl,int pr,ll val,int l,int r) {
  int cur = ++tot;
  tr[cur] = tr[pre];                      //新节点的左右儿子初始化前一棵树的数据
  if(pl <= l && pr >= r) {                //全覆盖
    tr[cur].val += (r-l+1)*val;           //标记留在节点上，查询时往下递归的过程遇到lazy则累加
    tr[cur].lazy += val;                  //标记
    return cur;
  }
  int m = (l+r)>>1;
  if(pl <= m) tr[cur].l = update(tr[pre].l,pl,pr,val,l,m);                     //递归左右区间
  if(pr >= m+1) tr[cur].r = update(tr[pre].r,pl,pr,val,m+1,r);
  pushup(cur,l,r);
  return cur;
}
ll query(int cur,int pl,int pr,ll laz,int l,int r) { //
  if(pl <= l && pr >= r) return tr[cur].val + laz * (r-l+1);                   //全部覆盖：计算结点val+懒标记*区间叶节点
  ll res = 0;
  laz += tr[cur].lazy;                 //累加懒标记
  int m = (l+r)>>1;
  if(pl <= m) res += query(tr[cur].l,pl,pr,laz,l,m);                          //累计左区间右区间返回的数值
  if(pr >= m+1) res += query(tr[cur].r,pl,pr,laz,m+1,r);
  return res;
}
int main()
{
  int n,m,l,r;
  ll d;
  char op[5];
  while(cin>>n>>m) {                  //序列长度，操作次数
    for(int i = 1; i<=n; i++) cin>>a[i];                                     //读取序列
    int T = 0,t;
    tot=0;
    root[T] = build(1,n);             //不是空树，叶节点放入数字
    while(m--) {
      scanf("%s",op);
      if(op[0] == 'C') {
        scanf("%d%d%lld",&l,&r,&d);
        T++;
        root[T] = update(root[T-1],l,r,d,1,n);                            //建新树，储存根节点
      }
      else if(op[0] == 'Q') {
        scanf("%d%d",&l,&r);
        printf("%lld\n",query(root[T],l,r,0,1,n));
      }
      else if(op[0] == 'H') {
        scanf("%d%d%d",&l,&r,&t); //t就是历史记录的根节点
        printf("%lld\n",query(root[t],l,r,0,1,n));
      }
      else scanf("%d",&T); //直接修改T，将历史记录修改成当前记录
    }
  }
  return 0 ;
}

笔记：区间更新这个通过主席树建树记录每次的更新节点，方便回溯历史纪录或者查询历史区间和。懒标记也是优化的一个重要环节，在递归时碰到懒标记就加上，在查询时，递归累加懒标记。