树状数组的基础应用

树状数组（Fenwick Tree）在处理区间更新、区间查询、单点查询等场景中非常高效。这里我们重点介绍两种进阶应用：

区间修改 + 单点查询
区间修改 + 区间查询

1. 区间修改 + 单点查询

问题描述

区间修改：将数组的某一段区间 $[l, r]$ 的所有元素增加一个值 $v$。
单点查询：查询数组的某个位置 $i$ 的元素值。

解决思路

我们可以将区间修改转化为两个前缀修改：

在 $l$ 处增加 $v$：意味着区间 $[l, n]$ 上的所有元素增加 $v$。
在 $r + 1$ 处减去 $v$：意味着区间 $[r + 1, n]$ 上的所有元素减少 $v$，保证区间 $[l, r]$ 的元素增加 $v$。

树状数组的构造

使用两个树状数组：

C1[]：用于维护修改的增量。
C2[]：辅助数组，用于计算前缀和的累加部分。

代码实现

#include <iostream>
using namespace std;

const int MAXN = 100010;
int C1[MAXN], C2[MAXN];  // 两个树状数组
int n;  // 数组长度

// lowbit 函数：计算二进制最低位 1 所代表的值
int lowbit(int x) {
    return x & (-x);
}

// 在树状数组 C 中更新第 k 个位置，增加 delta
void update(int C[], int k, int delta) {
    while (k <= n) {
        C[k] += delta;
        k += lowbit(k);
    }
}

// 查询树状数组 C 中的前缀和 [1, k]
int query(int C[], int k) {
    int sum = 0;
    while (k > 0) {
        sum += C[k];
        k -= lowbit(k);
    }
    return sum;
}

// 在区间 [l, r] 上增加 delta
void range_update(int l, int r, int delta) {
    update(C1, l, delta);
    update(C1, r + 1, -delta);
    update(C2, l, delta * (l - 1));
    update(C2, r + 1, -delta * r);
}

// 查询位置 i 的元素值
int point_query(int i) {
    return query(C1, i) * i - query(C2, i);
}

int main() {
    cin >> n;
    int q;  // 查询次数
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {  // 区间修改
            int l, r, delta;
            cin >> l >> r >> delta;
            range_update(l, r, delta);
        } else if (type == 2) {  // 单点查询
            int i;
            cin >> i;
            cout << point_query(i) << endl;
        }
    }
    return 0;
}

代码解析

update 函数：在树状数组中对某个位置进行更新。
range_update 函数：通过两个树状数组对区间进行修改。
point_query 函数：查询某个位置的元素值。

时间复杂度

单点更新：$O(\log n)$
单点查询：$O(\log n)$

2. 区间修改 + 区间查询

问题描述

区间修改：将数组的某一段区间 $[l, r]$ 的所有元素增加一个值 $v$。
区间查询：查询数组的某段区间 $[l, r]$ 的和。

解决思路

我们需要维护一个可以支持区间修改和区间查询的数据结构。我们仍然使用两个树状数组。

一个树状数组 C1[] 用于维护线性加权的增量。
另一个树状数组 C2[] 用于辅助计算累积增量。

公式推导

要查询区间 $[l, r]$ 的和，可以通过以下公式计算：

$$
\text{range_sum}(l, r) = \text{prefix_sum}(r) - \text{prefix_sum}(l - 1)
$$

其中，$\text{prefix_sum}(k)$ 是位置 $k$ 的前缀和，定义为：

$$
\text{prefix_sum}(k) = \text{query}(C1, k) \times k - \text{query}(C2, k)
$$

代码实现

#include <iostream>
using namespace std;

const int MAXN = 100010;
int C1[MAXN], C2[MAXN];  // 两个树状数组
int n;  // 数组长度

// lowbit 函数：计算二进制最低位 1 所代表的值
int lowbit(int x) {
    return x & (-x);
}

// 在树状数组 C 中更新第 k 个位置，增加 delta
void update(int C[], int k, int delta) {
    while (k <= n) {
        C[k] += delta;
        k += lowbit(k);
    }
}

// 查询树状数组 C 中的前缀和 [1, k]
int query(int C[], int k) {
    int sum = 0;
    while (k > 0) {
        sum += C[k];
        k -= lowbit(k);
    }
    return sum;
}

// 在区间 [l, r] 上增加 delta
void range_update(int l, int r, int delta) {
    update(C1, l, delta);
    update(C1, r + 1, -delta);
    update(C2, l, delta * (l - 1));
    update(C2, r + 1, -delta * r);
}

// 查询前缀和 [1, k]
int prefix_sum(int k) {
    return query(C1, k) * k - query(C2, k);
}

// 查询区间 [l, r] 的和
int range_query(int l, int r) {
    return prefix_sum(r) - prefix_sum(l - 1);
}

int main() {
    cin >> n;
    int q;  // 查询次数
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {  // 区间修改
            int l, r, delta;
            cin >> l >> r >> delta;
            range_update(l, r, delta);
        } else if (type == 2) {  // 区间查询
            int l, r;
            cin >> l >> r;
            cout << range_query(l, r) << endl;
        }
    }
    return 0;
}