线段树

  1 void build(int l,int r,int rt) {
  2     lazyp[rt]=0;
  3     lazym[rt]=1;
  4     if (l == r) {
  5         sum[rt] = a[l];
  6         return;
  7     }
  8     int mid = (l + r) >> 1;
  9     build(l, mid, rt << 1);
 10     build(mid + 1, r, rt << 1 | 1);
 11     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
 12 }
 13 
 14 void updata(int x,int d,int l,int r,int rt){
 15     if (l==r){
 16         sum[rt]+=d;
 17         return;
 18     }
 19     int mid=(l+r)>>1;
 20     updata(x,d,l,mid,rt<<1);
 21     updata(x,d,mid,r,rt<<1|1);
 22     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
 23 }
 24 
 25 void update(int l,int r,int d,int L,int R,int rt) {
 26     if (l <= L && R <= r) {
 27         sum[rt] += (r - l + 1) * d;
 28         lazy[rt] += d;
 29         return;
 30     }
 31     int mid = (l + r) >> 1;
 32     pushdown(mid - l + 1, r - mid, rt);
 33     if (l <= mid) updata(l, r, d, L, mid, rt << 1);
 34     if (r > mid) updata(l, r, d, mid+1, R, rt << 1 | 1);
 35     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
 36 }
 37 
 38 void update(int l,int r,int d,int L,int R,int rt) {
 39     if (l <= L && R <= r) {
 40         sum[rt] *=d;
 41         lazym[rt] *=d;
 42         lazyp[rt]*=d
 43         return;
 44     }
 45     int mid = (l + r) >> 1;
 46     pushdown(mid - l + 1, r - mid, rt);
 47     if (l <= mid) updata(l, r, d, L, mid, rt << 1);
 48     if (r > mid) updata(l, r, d, mid+1, R, rt << 1 | 1);
 49     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
 50 }
 51 
 52 void update(int l,int r,int d,int L,int R,int rt) {
 53     if (l <= L && R <= r) {
 54         sum[rt] += (r - l + 1) * d;
 55         lazyp[rt] += d;
 56         return;
 57     }
 58     int mid = (l + r) >> 1;
 59     pushdown(mid - l + 1, r - mid, rt);
 60     if (l <= mid) updata(l, r, d, L, mid, rt << 1);
 61     if (r > mid) updata(l, r, d, mid+1, R, rt << 1 | 1);
 62     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
 63 }
 64 
 65 void pushdown(int l,int r,int rt) {
 66     if (lazy[rt] == 0) {
 67         return;
 68     }
 69     lazy[rt << 1] += lazy[rt];
 70     lazy[rt << 1 | 1] += lazy[rt];
 71     lazy[rt] = 0;
 72     sum[rt << 1] += lazy[rt << 1] * l;
 73     sum[rt << 1 | 1] += lazy[rt << 1 | 1] * r;
 74 }
 75 
 76 void pushdown(int l,int r,int rt) {
 77     if (lazyp[rt]==0&&lazym[rt]==1){
 78         return;
 79     }
 80     sum[rt<<1]=(sum[rt<<1]*lazym[rt]+lazyp[rt]*l);
 81     sum[rt<<1|1]=(sum[rt<<1|1]*lazym[rt]+lazyp[rt]*l);
 82 
 83     lazym[rt << 1] =lazym[rt<<1]*lazym[rt];
 84     lazym[rt << 1|1] =lazym[rt<<1|1]*lazym[rt];
 85 
 86     lazyp[rt << 1] =lazyp[rt<<1]*lazym[rt]+lazyp[rt];
 87     lazyp[rt << 1|1] =lazyp[rt<<1|1]*lazym[rt]+lazyp[rt];
 88 
 89     lazyp[rt]==0;
 90     lazym[rt]==1;
 91 }
 92 
 93 int query(int l,int r,int L,int R,int rt) {
 94     if (l <= L && R <= r) {
 95         return sum[rt];
 96     }
 97     int mid = (l + r) >> 1;
 98     int ret = 0;
 99     pushdown(mid - l + 1, r - mid, rt);
100     if (l <= mid) ret += query(l, r, L, mid, rt << 1);
101     if (r > mid) ret += query(l, r, mid + 1, R, rt << 1 | 1);
102     return ret;
103 }