LIB::Imos
区間加算 、区間和取得
、更新処理
https://imoz.jp/algorithms/imos_method.html
累積和の機能を持つので累積和の上位互換として使える。
単純な累積和だと値の更新はできないが、このライブラリは任意のタイミングで値の更新が出来る。
メンバ関数
Imos(ll n); Imos(vector<T>& v);
サイズを指定してメモリを確保する
配列を入力して一括して累積和にすることも出来る
void add(ll i, T x); void add(ll l, ll r, T x);
配列[i]に値xを加算する（iが範囲外なら何もしない）
半開区間[l,r)に対して値xだけ加算する（lやrが範囲外のときは範囲内に丸めて処理する）
ll range(ll l, ll r);
半開区間[l,r)の合計値を取得する
void update(void);
でシミュレートする （この関数を呼ばないと累積和にならないので注意）
ソースコード
#include <bits/stdc++.h> namespace LIB { template<class T=ll>struct Imos { using ll=long long; ll sz; vector<T> a,s; Imos(ll n):sz(n),a(n),s(n) {} Imos(vector<T>& v):sz((ll)v.size()) { a.resize(sz),s=v; } void add(ll i, T x) { if(i<0||sz<=i) return; a[i]+=x; if(i==sz-1) return; a[i+1]-=x; } void add(ll l, ll r, T x) { if(r<=l) return; a[max(0ll,l)]+=x; if(sz<=r) return; a[r]-=x; } ll range(ll l, ll r) { if(l<0) l=0; if(sz<r) r=sz; if(r<=0||sz<=l||r<=l) return 0; return (l==0)?s[r-1]:s[r-1]-s[l-1]; } void update(void) { s[0]+=a[0]; for(ll i=1;i<sz;i++) s[i]+=s[i-1]+a[i]; fill(a.begin(),a.end(),0); } }; }
