Fenwick Tree(树状数组)总结

日付: 10月 23, 2018

# 树状数组总结
树状数组主要是以$Olog(N)$解决区间增添以及求和问题。和线段树相比运行效率一般更高，但泛用性差
## Plain(Single Modify, Range Query)
需要维护的数组是$A$，树状数组$BIT[i] = sum_{j=i-lowbit(i)+1}^iA[j]$表示以$i$为右端点长度为$lowbit(i)$的区间和。比如，$BIT[10100_2] = A[10001_2] + \cdots + A[10100_2]$。

这样在求$i$位置的前缀和(包括右端点)时，不断将$i$减去$lowbit$，将访问到的$BIT[i]$累加起来就好了。

当对$i$增加$x$时，需要找到所有的$i'$，使$i$在$[i'-lowbit(i')+1, i']$范围内，不断令$i = i + lowbit(i)$直到超出$BIT$数组范围，就可以找到所有满足条件的$i'$。(一个数加上$lowbit$就是把最右的连续的1去掉，并在左边补上一个1)
```c++
template <typename T> struct Fenwick {
    vector<T> V;
    Fenwick(int n): V(n) {}
    void add(size_t i, T x) { for (; i < V.size(); i += i&-i) V[i] += x; }
    T sum(int i) { T r = T(); for (--i; i; i -= i&-i) r += V[i]; return r; }
    T sum(int l, int r) { return sum(r) - sum(l); }
};
```
## 0-Based Indexing
上述写法有个问题就是数组必须从1开始，如果希望支持0下标，可以加个特判，更好的方法是更改树状数组结构。

$BIT[i]$表示以$i$为右端点，长度为$lowbit(\sim i)$的区间和。比如$10111_2$表示$[10000_2, 10111_2]$的区间和，求和时更新每次令$i=(i\&(i+1))-1$，相当于每次把最右第一个连续的0区间以及其左边一位取反，比如$10111_2$，连续操作后变为$01111_2$, $11111_2$，当全部都变成1时值小于0，结束循环。这种更新方法可以访问0下标。

修改时，每次令$i=i|(i+1)$，相当于每次把最右边的0变成1，直到超过区间范围。注意这里$i$最好是unsigned，因为如果最左边设为1时，如果是int就会变成负数，造成死循环(虽然这种情况不可能出现，因为不会开那么大的数组)。
```c++
template <typename T> struct Fenwick {
    vector<T> V;
    Fenwick(int n): V(n) {}
    void add(size_t i, T x) { for (; i < V.size(); i |= i + 1) V[i] += x; }
    T sum(int i) { 
        T r = T(); 
        for (--i; i >= 0; i = (i & (i + 1)) - 1) r += V[i]; 
        return r; 
    }
    T sum(int l, int r) { return sum(r) - sum(l); }
};
```
## Range Modify, Single Query 
想要实现`add(l, r, x)`，可以`add(l, x), add(r, -x)`，并用`sum(i)`表示$i$处的值。对$[l,r)$区间内的数取值时，前缀和都会增加$x$，而对$r$以后的数取值没有影响。这样树状数组相当于维护了一个差分数组，$BIT[i] = A[i] - A[i-1]，A[i] = \sum_{j=0}^i BIT[j]$
```c++
template <typename T> struct RSFenwick {
    vector<T> V;
    RSFenwick(int n): V(n) {}
    void _add(size_t i, T x) { for (; i < V.size(); i = i + 1) V[i] += x; }
    void add(size_t l, size_t r, T x) { _add(l, x), _add(r, -x); }
    T get(int i) { 
        T r = T(); 
        for (; i >= 0; i = (i & (i + 1)) - 1) r += V[i]; 
        return r; 
    }
};
```
## Range Modify and Query
和单点查询类似，还是维护差分数组，设为$D$，但是还要支持对于$A$数组的前缀和操作。
$S[i] = \sum_{j=0}^i A[j] = \sum_{j=0} ^i \sum_{k=0} ^j D[j] = \sum_{j=0} ^i (i-j+1)D[j] = (i+1) \sum_{j=0} ^i D[j] - \sum_{j=0} ^i  j \cdot D[j]$

所以可以维护两个数组，一个表示$D[i]$，另一个表示$-i \cdot D[i]$。
```c++
template <typename T> struct RangeFenwick {
    vector<T> V[2];
    RangeFenwick(int n) { for (int i = 0; i < 2; i++) V[i].assign(n, T()); }
    void _add(size_t i, T x, int k) { 
        for (; i < V[k].size(); i |= i + 1) V[k][i] += x; 
    }
    void add(int l, int r, T x) { 
        _add(l, x, 0); _add(r, -x, 0); _add(l, -x * l, 1); _add(r, x * r, 1); 
    }
    T _sum(int i, int k) { 
        T r = T(); 
        for (--i; i >= 0; i = (i & (i + 1)) - 1) r += V[k][i]; 
        return r; 
    }
    T sum(int i) { return i * _sum(i, 0) + _sum(i, 1); }
    T sum(int l, int r) { return sum(r) - sum(l); }
};
```
## Two Dimensional 
$BIT[i][j]$保存以$(i,j)$为右下角，宽$lowbit(j)$，高$lowbit(i)$的区块和。具体推导过程和一维类似，直接上代码

<details><summary>Plain</summary>

```c++
template <typename T> struct Fenwick2D {
    int n, m;
    vector<vector<T>> V;
    Fenwick2D(int n, int m): n(n), m(m), V(n, vector<T>(m)) {}
    void add(size_t i0, size_t j0, T x) {
        for (int i = i0; i < n; i |= i + 1) 
            for (int j = j0; j < m; j |= j + 1) 
                V[i][j] += x;
    }
    T sum(int i0, int j0) {
        T r = T();
        for (int i = i0 - 1; i >= 0; i = (i & (i + 1)) - 1)
            for (int j = j0 - 1; j >= 0; j = (j & (j + 1)) - 1) 
                r += V[i][j];
        return r;
    }
    T sum(int i, int j, int ii, int jj) { 
        return sum(ii, jj) + sum(i, j) - sum(i, jj) - sum(ii, j); 
    }
};
```
</details>

<details><summary>Range Modify, Single Query</summary>

```c++
template <typename T> struct RSFenwick2D {
    int n, m;
    vector<vector<T>> V;
    RSFenwick2D(int n, int m): n(n), m(m), V(n, vector<T>(m)) {}
    void _add(size_t i0, size_t j0, T x) {
        for (int i = i0; i < n; i |= i + 1)
            for (int j = j0; j < m; j |= j + 1)
                V[i][j] += x;
    }
    void add(size_t i, size_t j, size_t ii, size_t jj, T x) {
        _add(i, j, x), _add(i, jj, -x), _add(ii, j, -x), _add(ii, jj, x);
    }
    T get(int i, int j) {
        T r = T();
        for (int i = i0 - 1; i >= 0; i = (i & (i + 1)) - 1)
            for (int j = j0 - 1; j >= 0; j = (j & (j + 1)) - 1) 
                r += V[i][j];
        return r;
    }
};
```
</details>

<details><summary>Range Modify, Range Query</summary>

```c++
template <typename T> struct RangeFenwick2D {
    int n, m;
    vector<vector<T>> V[4];
    RangeFenwick2D(int n, int m): n(n), m(m) { 
        for (int i = 0; i < 4; i++) V[i].assign(n, vector<T>(m)); 
    }

void _add(size_t i0, size_t j0, T x) {
        for (int i = i0; i < n; i |= i + 1)
            for (int j = j0; j < m; j |= j + 1) {
                V[0][i][j] += x, V[1][i][j] -= x * i0;
                V[2][i][j] -= x * j0, V[3][i][j] += x * i0 * j0;
            }
    }
    void add(size_t i, size_t j, size_t ii, size_t jj, T x) {
        _add(i, j, x), _add(i, jj, -x), _add(ii, j, -x), _add(ii, jj, x);
    }
    T sum(int i0, int j0) {
        T r = T();
        for (int i = i0 - 1; i >= 0; i = (i & (i + 1)) - 1)
            for (int j = j0 - 1; j >= 0; j = (j & (j + 1)) - 1)
                r += V[0][i][j] * i0 * j0 + V[3][i][j] + \
                     j0 * V[1][i][j] + i0 * V[2][i][j];
        return r;
    }
    T sum(int i, int j, int ii, int jj) { 
        return sum(i, j) + sum(ii, jj) - sum(i, jj) - sum(ii, j); 
    }
};
```
</details>

KONGROOの基地

このブログを検索

Fenwick Tree(树状数组)总结

コメント

コメントを投稿