Friedforks's blog

Point Update Rage Sum

参考：

引入：

给定数组a，给个x,y，有一下操作：

a[x...y]的和
a[x]自增y

第一种就是【区间求和】，第二种就是【单点修改】。对应range sum还有point update。其实光是区间求和问题，我一个前缀和也能做，但是带上修改的就不行了，比较固定，所以我们需要更高级的一些数据结构来存区间信息。

Feinwick Tree （树状数组）

首先出场的是树状数组，他比线段树要难理解，但是代码简单。

下图就是树状数组的一个例子（来自oi-wiki）：

性质

这里a就是原数组，c就是树状数组。c中存的是a中某段的和，但是具体怎么知道c[i]对应的是哪段a[x....y]呢？首先，我们可以发现，a[x....y]中的y一定等于i，例如c[4]=\sum a[1]...a[4]，所以关键是x，也就是左端点。

对于这个问题，我们先看上图有什么规律：

第一层：1,3,5,7，也就都是奇数
第二层：2,6
第三层：4
第四层：8

有点规律，但不多。我们可以看到每一层代表了他管辖范围的长度，例如第3层的c[4]管辖a[1...4]。所以第n层的c[i]管辖的就是a[i-n,i]。现在我们的问题变成了：给定c[i]，如何确定他在哪层？

我们需要引入二进制来考虑，其实这也是这个算法比较精巧的点，再列举一下：

第一层
- (1)_2=1
- (3)_2=11
- (5)_2=101
- (7)_2=111
- 他们都是奇数，结尾都是1
第二层
- (2)_2=10
- (6)_2=1010
- 结尾都是10
第三层
- (4)_2=100
- 结尾是100，数组长度有点小但如果边长点后面的第三层也是结尾100，这里就不举例了
第四层
- (8)_2=1000
- 结尾是1000

这下看懂了，给定c[i]，他的层数就是他二进制截取最后一个1和后面的0。 我们可以使用lowbit来计算：

lowbit

lowbit(x)的意思就是二进制截取最后一个1和后面的0。根据位运算知识，lowbit(x)=x&(-x)，具体原因不细说了温习一下位运算就好。

代码：

int lowbit(int x) {
  // x 的二进制中，最低位的 1 以及后面所有 0 组成的数。
  // lowbit(0b01011000) == 0b00001000
  //          ~~~~^~~~
  // lowbit(0b01110010) == 0b00000010
  //          ~~~~~~^~
  return x & -x;
}

注意 lowbit截取的不是最后一个1的位置，而是1000....这个整体组成的2。

得出结论：c[x]=\sum^x_{i=x-lowbit(x)+1}a[i]，这就是树状数组每个元素存的。

查询

问题：给定x,y，求a[x...y]的和。如果他问的是a[1...8]，那么答案很简单就是c[8]。但是如果是a[2...8]那么还要给他这个区间段拆分为c[8]-a[1]，换个例子问a[2...7]，而我们在前缀和里知道：a[2..7]=prefix[7]-prefix[1]，所以我们只要有一个函数能处理a[1...x]就可以了，然后和前缀和一样剪掉多算的prefix[1]

所以思路就是给定查询区间a[1...y]，从 i=y 开始往左跳，每次 i=i-lowbit(i)，然后在 i=0时终止。

代码如下：

int sum(int l, int r) {
    int i = r;
    int acc = 0;
    for (; i > 0; i = i - lowbit(i)) {
        acc += f[i];
    }
}

查询时间复杂度证明

（来自 oi-wiki）

考虑 r 和 l 不同的最高位，一定有 r 在这一位上为 1，l 在这一位上为 0（因为 r \geq l）。

如果 r 在这一位的后面仍然有 1，一定有 r - \text{lowbit}(r) \geq l，所以下一步一定是把 r 的最低位 1 填为 0；如果 r 的这一位 1 就是 r 的最低位 1，无论是 r \gets r - \text{lowbit}(r) 还是 r \gets r - 1，r 的这一位 1 一定会变为 0。

因此，经过至多 \log n 次变换后，r 和 l 不同的最高位一定可以下降一位。所以，总时间复杂度是 \Theta(\log^2 n)。

单点修改

单点修改的思路，就是区间查询倒过来。

给定几种更新更新，其中都可以通过一些变形成为第一种：

a[x]=a[x]+k
a[x]=k\Rightarrow a[x]=a[x]+(p-a[x]),k=(p-a[x])
a[x]=a[x]\times p\Rightarrow a[x]=a[x]+(a[x]\times p-a[x]),k=(a[x]\times p-a[x])

所以只需要考虑第一种的代码怎么写。其实就是当a[x]=a[x]+k的时候，管辖a[x]的c需要更新。而管辖a[x]的只有c[x+n\times lowbit(x)]

代码：

void update(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        c[i] += k;
    }
}

修改时间复杂度证明

（来自 oi-wiki）

对于单点修改操作：跳父亲时，访问到的高度一直严格增加，且始终有 x \leq n。由于点 x 的高度是 \log_2 \text{lowbit}(x)，所以跳到的高度不会超过 \log_2 n，所以访问到的 c 的数量是 \log n 级别。

因此，单次单点修改复杂度是 \Theta(\log n)。

建树

建树的操作可以被转化为n个单点修改，复杂度为O(n\log n)，就不写代码了。

完整模板

// Template-based Fenwick Tree class
template <typename T>
class FenwickTree {
private:
    vector<T> c; // Fenwick Tree array
    int n;       // Size of the array

    // Function to calculate the lowest bit (lowbit)
    // lowbit(x) = the lowest set bit of x and the trailing 0s
    int lowbit(int x) {
        return x & -x;
    }

public:
    // Constructor: initializes the Fenwick Tree with size `size`
    FenwickTree(int size) {
        n = size;
        c.resize(n + 1, 0); // Fenwick Tree indices start from 1
    }

    // Point update: add `k` to position `x`
    void update(int x, T k) {
        for (int i = x; i <= n; i += lowbit(i)) {
            c[i] += k;
        }
    }

    // Prefix sum query: calculate the sum of elements a[1] to a[x]
    T query(int x) {
        T sum = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            sum += c[i];
        }
        return sum;
    }

    // Range sum query: calculate the sum of elements a[l] to a[r]
    T rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }

    // Build the Fenwick Tree from an input array
    void build(const vector<T>& a) {
        for (int i = 1; i <= n; ++i) {
            update(i, a[i - 1]); // Convert 0-based index of `a` to 1-based index
        }
    }

    // Debugging function to print the Fenwick Tree array
    void printTree() {
        for (int i = 1; i <= n; ++i) {
            cout << "c[" << i << "] = " << c[i] << endl;
        }
    }
};

使用例：

```cpp
int main() {
    // Example: input array
    vector<int> a = {1, 2, 3, 4, 5};
    int n = a.size();

    // Initialize Fenwick Tree with the size of the array
    FenwickTree<int> fenwick(n);

    // Build the Fenwick Tree from the input array
    fenwick.build(a);

    // Query the sum of a range
    cout << "Sum of range [2, 4]: " << fenwick.rangeQuery(2, 4) << endl; // Output: 9

    // Perform a point update
    fenwick.update(3, 5); // Add 5 to a[3]

    // Query the range sum again after the update
    cout << "Sum of range [2, 4] after update: " << fenwick.rangeQuery(2, 4) << endl; // Output: 14

    return 0;
}

模版题1：P3374 【模板】树状数组 1 - 洛谷

代码：

/*
 * Created by: Chixiyu
 * Date: 2025-02-19
 */
#include <bits/stdc++.h>
using namespace std;

template <typename T> class FenwickTree {
  private:
    vector<T> c;
    int n;

    // Function to calculate the lowest bit (lowbit)
    int lowbit(int x) { return x & -x; }

  public:
    // Constructor: initializes the Fenwick Tree with size `size`
    FenwickTree(int size) {
        n = size;
        c.resize(n + 1, 0);
    }

    // Point update: add `k` to position `x`
    void update(int x, T k) {
        for (int i = x; i <= n; i += lowbit(i)) {
            c[i] += k;
        }
    }

    // Prefix sum query: calculate the sum of elements a[1] to a[x]
    T query(int x) {
        T sum = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            sum += c[i];
        }
        return sum;
    }

    // Range sum query: calculate the sum of elements a[l] to a[r]
    T rangeQuery(int l, int r) { return query(r) - query(l - 1); }

    // Build the Fenwick Tree from an input array
    void build(const vector<T> &a) {
        for (int i = 1; i <= n; ++i) {
            update(i, a[i - 1]);
        }
    }

    // Debugging function to print the Fenwick Tree array
    void printTree() {
        for (int i = 1; i <= n; ++i) {
            cout << "c[" << i << "] = " << c[i] << endl;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto &it : a)
        cin >> it;
    FenwickTree<int> ft(n);
    ft.build(a);
    while (m--) {
        int operation;
        cin >> operation;
        if (operation == 1) { // point update
            int x, k;
            cin >> x >> k;
            ft.update(x, k);
        } else { // range sum
            int l, r;
            cin >> l >> r;
            cout << ft.rangeQuery(l, r) << endl;
        }
    }
    return 0;
}

Point Update Range Sum