萌新线段树求条

#include <iostream>

#include <vector>

#define endl '\n'

#define ls(x) x << 1
#define rs(x) x << 1 | 1

using namespace std;

const int N = 1e5 + 5;

struct Node{
  int v, tag;
}t[( N << 2 )];

int n, m, a[N];

void build(int l, int r, int p){
  if(l == r){
    t[p].v = a[l];
    return ;
  }
  int mid = l + r >> 1;
  build(l, mid, ls(p)), build(mid + 1, r, rs(p));
  t[p].v = t[ls(p)].v + t[rs(p)].v;
}

void push_down(int p, int lenl, int lenr){
  t[ls(p)].v += t[p].tag * lenl, t[rs(p)].v += t[p].tag * lenr;
  t[ls(p)].tag += t[p].tag, t[rs(p)].tag += t[p].tag;
  t[p].tag = 0;
}

void update(int l, int r, int nl, int nr, int p, int w){
  if(nl > nr || l > nr || r < nl) return ;
  if(nl >= l && nr <= r){
    t[p].tag += w, t[p].v += (nr - nl + 1) * w;
    return ;
  }
  int mid = nl + nr >> 1;
  if(t[p].tag > 0)
    push_down(p, mid - nl + 1, nr - mid - 1);
  update(l, r, nl, mid, ls(p), w);
  update(l, r, mid + 1, nr, rs(p), w);
  t[p].v = t[ls(p)].v + t[rs(p)].v;
}

int query(int l, int r, int nl, int nr, int p){
  if(nl > nr || nl > r || nr < l) return 0;
  if(nl >= l && nr <= r) return t[p].v;
  int mid = nl + nr >> 1;
  if(t[p].tag > 0)
    push_down(p, mid - nl + 1, nr - mid - 1);
  int sum = query(l, r, nl, mid, ls(p));
  sum += query(l, r, mid + 1, nr, rs(p));
  return sum;
}

int main(){
  ios :: sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for(int i = 1, x; i <= n; ++i){
    cin >> a[i];
  }
  build(1, n, 1);
  while(m--){
    int op, x, y, k;
    cin >> op >> x >> y;
    if(op == 1){
      cin >> k;
      update(x, y, 1, n, 1, k);
    }else{
      cout << query(x, y, 1, n, 1) << endl;
    }
  }
  return 0;
}