poyo-poyo
4/2/2017 - 11:21 AM

SegmentTree一般について ・indexは0から始める。 ・[l, r)で扱う。 Nは制約の上限より余分にとっておいてよい。（木が下に深くなる）

SegmentTree一般について ・indexは0から始める。 ・[l, r)で扱う。

Nは制約の上限より余分にとっておいてよい。（木が下に深くなる）

RangeAdd&SumQuery.cpp
content_copyfile_download
/*
遅延SegmentTree
・区間に加算
・区間の総和
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G
*/

#include<iostream>
#include<vector>

using namespace std;
#define int long long

// staticつけるとクラス内の他の関数から見える
struct SegmentTree{

   static const int N=1<<17;// 区間の幅の最大
   static const int Z=0;
   vector<int> seg, lazy;
   SegmentTree(){
      seg.resize(2*N-1, 0);// 木の全ノードの個数 
      lazy.resize(2*N-1, 0);
   }

   void refresh(int i, int l, int r){
      if(lazy[i]){
         seg[i]+=lazy[i]*(r-l);// いい感じに解消する
         if(r-l>1){// 葉チェック
            lazy[2*i+1]+=lazy[i];
            lazy[2*i+2]+=lazy[i];
         }
         lazy[i]=0;
      }
   }

   void add(int a, int b, int x, int i=0, int l=0, int r=N){
      refresh(i, l, r);// とりあえず解消しとく
      if(b<=l or r<=a){
         return;
      }else if(a<=l and r<=b){
         lazy[i]+=x;// ここきらい
         refresh(i, l, r);// 不安なのでもう一回
      }else{
         int m=(r+l)/2;
         add(a, b, x, 2*i+1, l, m);
         add(a, b, x, 2*i+2, m, r);
         seg[i]=seg[2*i+1]+seg[2*i+2];// いい感じに書く
      }
   }

   int sum(int a, int b, int i=0, int l=0, int r=N){
      refresh(i, l, r);// とりあえず解消しとく
      if(b<=l or r<=a){
         return Z;
      }else if(a<=l and r<=b){
         return seg[i];
      }else{
         int m=(r+l)/2;
         int vl=sum(a, b, 2*i+1, l, m);
         int vr=sum(a, b, 2*i+2, m, r);
         return vl+vr;// いい感じに書く
      }
   }

};

signed main(){

   int N, Q;
   cin>> N>> Q;
   SegmentTree st;
   while(Q--){
      int q; cin>> q;
      if(q==0){
         int s, t, x;
         cin>> s>> t>> x;
         st.add(s-1, t, x);
      }else{
         int s, t;
         cin>> s>> t;
         cout<< st.sum(s-1, t)<< endl;
      }
   }

   return 0;
}