This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include "../template.hpp" #include "../SegmentTree/SegmentTree.hpp" signed main(){ int n,q;cin>>n>>q; auto segfunc=[](ll a,ll b){ return a+b; }; SegmentTree<ll> seg(n,segfunc,0); rep(i,n){ ll a;cin>>a; seg.set(i,a); } seg.build(); for(;q--;){ int type;cin>>type; if(type==0){ int p;ll x;cin>>p>>x; seg.update(p,seg.query(p,p+1)+x); } else{ int l,r;cin>>l>>r; cout<<seg.query(l,r)<<endl; } } return 0; }
#line 1 "test/yosupo_Point-Add-Range-Sum.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #line 1 "template.hpp" #include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } #line 4 "test/yosupo_Point-Add-Range-Sum.test.cpp" #line 1 "SegmentTree/SegmentTree.hpp" template<typename Monoid> struct SegmentTree{ using F=function<Monoid(Monoid,Monoid)>; private: int sz; vector<Monoid> seg; Monoid query(int a,int b,int k,int l,int r){ if(a<=l and r<=b) return seg[k]; if(b<=l or r<=a) return M0; Monoid L=query(a,b,2*k,l,(l+r)/2); Monoid R=query(a,b,2*k+1,(l+r)/2,r); return f(L,R); } template<typename C> int find_first(int a,const C &check,Monoid &acc,int k,int l,int r){ if(k>=sz){ acc=f(acc,seg[k]); if(check(acc)) return -1; else return k-sz; } int m=(l+r)/2; if(m<=a) return find_first(a,check,acc,2*k+1,m,r); if(a<=l and check(f(acc,seg[k]))){ acc=f(acc,seg[k]); return -1; } int x=find_first(a,check,acc,2*k+0,l,m); if(x>=0) return x; return find_first(a,check,acc,2*k+1,m,r); } template<typename C> int find_last(int b,const C &check,Monoid &acc,int k,int l,int r){ if(k>=sz){ acc=f(acc,seg[k]); if(check(acc)) return -1; else return k-sz+1;//ここはfalse, +1した位置はtrue } int m=(l+r)/2; if(b<=m) return find_last(b,check,acc,2*k,l,m); if(r<=b and check(f(acc,seg[k]))){ acc=f(acc,seg[k]); return -1; } int x=find_last(b,check,acc,2*k+1,m,r); if(x>=0) return x; return find_last(b,check,acc,2*k,l,m); } public: F f; Monoid M0;// モノイドの元 SegmentTree(int n, F f_, Monoid M0_) : f(f_), M0(M0_) { sz=1; while(sz<n)sz<<=1; seg.assign(2*sz,M0); } void set(int k,Monoid x){ seg[k+sz]=x; } void build(){ for(int k=sz-1;k>0;k--) seg[k]=f(seg[2*k],seg[2*k+1]); } void update(int k,Monoid x){ k+=sz; seg[k]=x; k>>=1; for(;k;k>>=1) seg[k]=f(seg[2*k],seg[2*k+1]); } Monoid query(int a,int b){ return query(a,b,1,0,sz); } Monoid operator[](const int &k)const{ return seg[k+sz]; } // http://codeforces.com/contest/914/submission/107505449 // max x, check(query(a, x)) = true template<typename C> int find_first(int a,const C &check){ Monoid val=M0; return find_first(a,check,val,1,0,sz); } // http://codeforces.com/contest/914/submission/107505582 // min x, check(query(x, b)) = true template<typename C> int find_last(int b,C &check){ Monoid val=M0; return find_last(b,check,val,1,0,sz); } }; #line 6 "test/yosupo_Point-Add-Range-Sum.test.cpp" signed main(){ int n,q;cin>>n>>q; auto segfunc=[](ll a,ll b){ return a+b; }; SegmentTree<ll> seg(n,segfunc,0); rep(i,n){ ll a;cin>>a; seg.set(i,a); } seg.build(); for(;q--;){ int type;cin>>type; if(type==0){ int p;ll x;cin>>p>>x; seg.update(p,seg.query(p,p+1)+x); } else{ int l,r;cin>>l>>r; cout<<seg.query(l,r)<<endl; } } return 0; }