This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub crackersamdjam/Codebook
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include "../content/data_structures/bit.h" int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); int n, q; cin>>n>>q; bit<ll> t; t.init(n+1, 0, [](auto x, auto y){ return x+y;}); for(int i = 1,a; i <= n; i++){ cin>>a; t.update(i, a); } while(q--){ int op; cin>>op; if(op == 0){ int i, x; cin>>i>>x; t.update(i+1, x); } else{ int l, r; cin>>l>>r; cout<<t.query(r)-t.query(l)<<'\n'; } } }
#line 1 "tests/bit.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #line 1 "content/utils/template.h" /** * @brief My starter code */ #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end()); #ifdef LOCAL template<typename T> void pr(T a){std::cerr<<a<<std::endl;} template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);} #else template<typename... Args> void pr(Args... args){} #endif using namespace std; using ll = long long; using pii = pair<int, int>; #line 3 "content/data_structures/bit.h" /** * @brief Binary Indexed Tree * @docs docs/bit.md */ template<class T> struct bit{ int SZ; vector<T> bit; function<T(T, T)> merge; void init(int n, T def, function<T(T, T)> f){ SZ = n; bit.resize(SZ, def); merge = f; } void update(int i, T v){ for(; i < SZ; i += i&-i) bit[i] = merge(bit[i], v); } T query(int i){ T x = bit[0]; for(; i; i -= i&-i) x = merge(x, bit[i]); return x; } }; template<class T> struct range_bit{ bit<T> T1, T2; function<T(T, T)> unmerge; void init(int n, T def, function<T(T, T)> f, function<T(T, T)> g){ T1.init(n, def, f); T2.init(n, def, f); unmerge = g; } T query(int i){ return i*T1.query(i)-T2.query(i); } T query(int l, int r){ return unmerge(query(r), query(l-1)); } void update(int l, int r, T v){ T1.update(l, v); T1.update(r+1, -v); T2.update(l, v*(l-1)); T2.update(r+1, -v*r); } void update(int l, T v){ update(l, l, v); } }; #line 3 "tests/bit.test.cpp" int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); int n, q; cin>>n>>q; bit<ll> t; t.init(n+1, 0, [](auto x, auto y){ return x+y;}); for(int i = 1,a; i <= n; i++){ cin>>a; t.update(i, a); } while(q--){ int op; cin>>op; if(op == 0){ int i, x; cin>>i>>x; t.update(i+1, x); } else{ int l, r; cin>>l>>r; cout<<t.query(r)-t.query(l)<<'\n'; } } }