Loading... ## 树状数组 ```cpp class BIT { public: int n; // n为数组最大的有效下标 int len; // len为树状数组的最大长度，为n的2倍 vector<int> tree; int lowbit(int x){ return x&(-x); } BIT(){ n = len = 0; } BIT(vector<int> &ori){ n = ori.size(); len = n * 2; tree.resize(len+1); for(int i=0;i<n;++i) add(i, ori[i]); } // 在原数组的[i]处增加v void add(int i, int v){ i++; // 树状数组下标是从1开始 while(i <= n){ tree[i] += v; i += lowbit(i); } } // 获取原数组0~i的前缀和 int sum(int i){ i++; int res = 0; while(i>0) { res += tree[i]; i -= lowbit(i); } return res; } }; ``` ### 二维树状数组 ```cpp class BIT2d { public: int m, n; vector<vector<int>> tree; int lowbit(int x){ return x&(-x); } BIT2d(){ m = n = 0; } BIT2d(vector<vector<int>> &ori){ m = ori.size(); n = ori[0].size(); tree.resize(m*2+1, vector<int>(n*2+1)); for(int i=0;i<m;++i) for(int j=0;j<n;++j) add(i, j, ori[i][j]); } void add(int i, int j, int v){ i++; j++; while(i <= m){ int tj = j; while(tj <= n){ tree[i][tj] += v; tj += lowbit(tj); } i += lowbit(i); } } int sum(int i, int j){ i++; j++; int res = 0; while(i>0) { int tj = j; while(tj>0){ res += tree[i][tj]; tj -= lowbit(tj); } i -= lowbit(i); } return res; } }; ``` ## 快速乘 ```cpp long long ksc(long long a, long long b, long long mod){ long long res = 0; while(b){ if(b&1) res = (res + a)%mod; a <<= 1; a %= mod; b >>= 1; } return res; } ``` ## 快速幂 ```cpp long long pow(long long n, long long m, long long mod){ long long res=1, a=n; while(m){ if(m & 1) res = (a * res) % mod; a=(a * a) % mod; m>>=1; } return res; } ``` 最后修改：2021 年 10 月 05 日 12 : 46 AM © 允许规范转载