class FenwickTree{ private int _n; private long[] data; public FenwickTree(int n){ this._n = n; data = new long[n]; } /** * @verified https://atcoder.jp/contests/practice2/tasks/practice2_b * @submission https://atcoder.jp/contests/practice2/submissions/16580495 */ public FenwickTree(long[] data) { this(data.length); build(data); } public void set(int p, long x){ add(p, x - get(p)); } public void add(int p, long x){ assert(0<=p && p<_n); p++; while(p<=_n){ data[p-1] += x; p += p&-p; } } public long sum(int l, int r){ assert(0<=l && l<=r && r<=_n); return sum(r)-sum(l); } public long get(int p){ return sum(p, p+1); } private long sum(int r){ long s = 0; while(r>0){ s += data[r-1]; r -= r&-r; } return s; } private void build(long[] dat) { System.arraycopy(dat, 0, data, 0, _n); for (int i=1; i<=_n; i++) { int p = i+(i&-i); if(p<=_n){ data[p-1] += data[i-1]; } } } }