树状数组的区间修改和区间查询

树状数组（Binary Indexed Tree，BIT）是一种数据结构，用于维护序列的前缀和。它可以支持单点修改和区间查询，但是不支持区间修改。不过可以通过巧妙的方式将区间修改转化为单点修改，从而实现区间修改。

区间修改：我们可以将区间修改转化为单点修改，具体方法是将区间修改拆成两次单点修改：先将区间左端点减一，再将区间右端点加一。这样的话，查询时只需要查询右端点的前缀和，再减去左端点的前缀和即可得到区间和。

区间查询：查询区间和可以通过前缀和相减得到。具体方法是查询右端点的前缀和，再减去左端点减一的前缀和即可得到区间和。

具体实现可以参考下面的代码：

#include <iostream>
#include <vector>

using namespace std;

class BIT {
public:
    BIT(int n) : sums(n + 1) {}

    void update(int i, int delta) {
        while (i < sums.size()) {
            sums[i] += delta;
            i += lowbit(i);
        }
    }

    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += sums[i];
            i -= lowbit(i);
        }
        return sum;
    }

private:
    vector<int> sums;

    int lowbit(int x) {
        return x & (-x);
    }
};

class RangeBIT {
public:
    RangeBIT(int n) : bit1(n), bit2(n) {}

    void update(int i, int j, int delta) {
        bit1.update(i, delta);
        bit1.update(j + 1, -delta);
        bit2.update(i, delta * (i - 1));
        bit2.update(j + 1, -delta * j);
    }

    int query(int i, int j) {
        return prefix_sum(j) - prefix_sum(i - 1);
    }

private:
    BIT bit1, bit2;

    int prefix_sum(int i) {
        return bit1.query(i) * i - bit2.query(i);
    }
};

注意，这里的 BIT 是用于维护前缀和的，而 RangeBIT 是用于维护区间和的。区间修改时，bit1 用于维护前缀和，bit2 用于维护前缀和乘以下标的和。查询时，先计算出区间的前缀和，再减去左端点减一的前缀和乘以左端点即可得到区间和。