解决问题类型:
单点更新, 前缀查询, 很简单地拓展到 2 维
复杂度即代码:
- // 压行
- #define lowbit(x) ((x)&(-(x)))
- void add(int x, int y) { for (; x <= idx; x += lowbit(x)) f[x] += y; }
- int sum(int x) { int ans = 0; for (; x; x -= lowbit(x)) ans += f[x]; return ans; }
- // 从 0 开始的 BIT(下标)
- struct FenwickTree {
- vector<int> bit; // binary indexed tree
- int n;
- FenwickTree(int n) {
- this->n = n;
- bit.assign(n, 0);
- }
- FenwickTree(vector<int> a) : FenwickTree(a.size()) {
- for (size_t i = 0; i <a.size(); i++)
- add(i, a[i]);
- }
- int sum(int r) {
- int ret = 0;
- for (; r>= 0; r = (r & (r + 1)) - 1)
- ret += bit[r];
- return ret;
- }
- int sum(int l, int r) {
- return sum(r) - sum(l - 1);
- }
- void add(int idx, int delta) {
- for (; idx <n; idx = idx | (idx + 1))
- bit[idx] += delta;
- }
- };
- struct FenwickTree2D {
- vector<vector<int>> bit;
- int n, m;
- // init(...) { ... }
- int sum(int x, int y) {
- int ret = 0;
- for (int i = x; i>= 0; i = (i & (i + 1)) - 1)
- for (int j = y; j>= 0; j = (j & (j + 1)) - 1)
- ret += bit[i][j];
- return ret;
- }
- void add(int x, int y, int delta) {
- for (int i = x; i <n; i = i | (i + 1))
- for (int j = y; j < m; j = j | (j + 1))
- bit[i][j] += delta;
- }
- };
高维:
- // 三维模板
- struct BIT {
- int a[maxn];
- inline int lowbit(int x) { return x & -x; }
- inline int gid(int x, int y, int z) {
- return x * m * h + y * h + z;
- }
- void clear() {
- for (int i = 0; i < maxn; i++) a[i] = -inf;
- }
- void update(int x, int y, int z, int val) {
- for (int i = x; i <= n; i += lowbit(i)) {
- for (int j = y; j <= m; j += lowbit(j)) {
- for (int k = z; k <= h; k += lowbit(k)) {
- gmax(a[gid(i, j, k)], val);
- }
- }
- }
- }
- int query(int x, int y, int z) {
- int r = -inf;
- for (int i = x; i; i -= lowbit(i)) {
- for (int j = y; j; j -= lowbit(j)) {
- for (int k = z; k; k -= lowbit(k)) {
- r = max(r, a[gid(i, j, k)]);
- }
- }
- }
- return r;
- }
- } f[8];
- // 区间询问单点查询
- void add(int idx, int val) {
- for (++idx; idx < n; idx += idx & -idx)
- bit[idx] += val;
- }
- void range_add(int l, int r, int val) {
- add(l, val);
- add(r + 1, -val);
- }
- int point_query(int idx) {
- int ret = 0;
- for (++idx; idx> 0; idx -= idx & -idx)
- ret += bit[idx];
- return ret;
- }
- python
- //g(i) = i - (i ~&~ (-i).
- def sum(int r):
- res = 0
- while (r> 0):
- res += t[r]
- r = g(r)
- return res
- def increase(int i, int delta):
- for all j with g(j) <i <= j:
- t[j] += delta
区间询问查询
- def add(b, idx, x):
- while idx <= N:
- b[idx] += x
- idx += idx & -idx
- def range_add(l,r,x):
- add(B1, l, x)
- add(B1, r+1, -x)
- add(B2, l, x*(l-1))
- add(B2, r+1, -x*r)
- def sum(b, idx):
- total = 0
- while idx> 0:
- total += b[idx]
- idx -= idx & -idx
- return total
- def prefix_sum(idx):
- return sum(B1, idx)*idx - sum(B2, idx)
- def range_sum(l, r):
- return sum(r) - sum(l-1)
例题
- UVA 12086 - Potentiometers
- LOJ 1112 - Curious Robin Hood
- LOJ 1266 - Points in Rectangle
- Codechef - SPREAD http://www.codechef.com/problems/SPREAD
- SPOJ - CTRICK http://www.spoj.com/problems/CTRICK/
- SPOJ - MATSUM http://www.spoj.com/problems/MATSUM/
- SPOJ - DQUERY http://www.spoj.com/problems/DQUERY/
- SPOJ - NKTEAM http://www.spoj.com/problems/NKTEAM/
- SPOJ - YODANESS http://www.spoj.com/problems/YODANESS/
- SRM 310 - FloatingMedian
- SPOJ - Ada and Behives http://www.spoj.com/problems/ADABEHIVE/
- Hackerearth - Counting in Byteland
- DevSkills - Shan and String
- Codeforces - Little Artem and Time Machine http://codeforces.com/contest/669/problem/E
- Codeforces - Hanoi Factory http://codeforces.com/contest/777/problem/E
- SPOJ - Tulip and Numbers http://www.spoj.com/problems/TULIPNUM/
- SPOJ - SUMSUM http://www.spoj.com/problems/SUMSUM/
- SPOJ - Sabir and Gifts http://www.spoj.com/problems/SGIFT/
- SPOJ - The Permutation Game Again http://www.spoj.com/problems/TPGA/
- SPOJ - Zig when you Zag http://www.spoj.com/problems/ZIGZAG2/
- SPOJ - Cryon http://www.spoj.com/problems/CRAYON/
- SPOJ - Weird Points http://www.spoj.com/problems/DCEPC705/
- SPOJ - Its a Murder http://www.spoj.com/problems/DCEPC206/
- SPOJ - Bored of Suffixes and Prefixes http://www.spoj.com/problems/KOPC12G/
- SPOJ - Mega Inversions http://www.spoj.com/problems/TRIPINV/
- Codeforces - Subsequences http://codeforces.com/contest/597/problem/C
- Codeforces - Ball http://codeforces.com/contest/12/problem/D
- GYM - The Kamphaeng Phet's Chedis http://codeforces.com/gym/101047/problem/J
- Codeforces - Garlands http://codeforces.com/contest/707/problem/E
- Codeforces - Inversions after Shuffle http://codeforces.com/contest/749/problem/E
- GYM - Cairo Market
- Codeforces - Goodbye Souvenir http://codeforces.com/contest/849/problem/E
- SPOJ - Ada and Species http://www.spoj.com/problems/ADACABAA/
- Codeforces - Thor https://codeforces.com/problemset/problem/704/A
- Latin American Regionals 2017 - Fundraising http://matcomgrader.com/problem/9346/fundraising/
代码
来源: http://www.bubuko.com/infodetail-3158699.html