BIT

树状数组 Binary Index Tree/Fenwick Tree 1d 单点修改，区间询问 // T must + - // id 1~n template<typename T,size_t M,typename OpPlus=plus<T>,typename OpMinus=minus<T>> struct BIT { static int lowbit(int x) { return x&(-x); } constexpr static OpPlus opp{}; constexpr static OpMinus opm{}; static T tmp[M+1]; T tree[M+1]; // tree[i] -> sum of [i-lowbit(i)+1,i] int n; void init(int n_) { n=n_; for(int i=1;i<=n;i++) tree[i]=T(0); } void init(int n_,T v[]) // v[0 ~ n_-1] { n=n_; tmp[0]=T(0); for(int i=1;i<=n;i++) tmp[i]=opp(tmp[i-1],v[i]); for(int i=1;i<=n;i++) tree[i]=opm(tmp[i],tmp[i-lowbit(i)]); // for(int i=0;i<n;i++) add(i,v[i]); } void add(int p,T V) { for(;p<=n;p+=lowbit(p)) …