专栏文章

题解：P3368 【模板】树状数组 2

mmazhenhao0235
P3368题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipvz0c1
此快照首次捕获于
2025/12/03 18:50
3 个月前
此快照最后确认于
2025/12/03 18:50
3 个月前
查看原文

P3368 题解：树状数组2

题目传送门

题目描述

给定一个长度为 nn 的数组 ff ，以及 mm 次操作。操作分为两种：
  1. 区间修改：将数组 ff 中下标在 [x,y][x, y] 范围内的元素都加上 zz。
  2. 单点查询：查询数组 ff 中下标为 xx 的元素的值。

解题思路

这道题可以使用树状数组来高效地处理区间修改和单点查询。树状数组是一种支持单点修改和区间查询的数据结构，但通过差分的思想，我们可以将其扩展为支持区间修改和单点查询。

代码解析

树状数组的定义：

fa[N]fa[N]：树状数组，用于存储差分数组。
lowbit(x)lowbit(x) ：返回 xx 的二进制表示中最低位的 11 所对应的值。
add(x,k)add(x, k) ：在树状数组的第 xx 个位置加上 kk ，并更新其父节点。
search(x)search(x) ：查询树状数组中前 xx 个元素的和。

初始化：

读取数组 ff 的初始值。

处理操作：

区间修改：对于操作 11 xx yy zz ，我们通过差分的思想，在 xx 位置加上 zz，在 y+1y+1 位置减去 zz 。这样，查询时就可以通过前缀和得到每个位置的实际值。
单点查询：对于操作 22 xx，我们查询树状数组中前 xx 个元素的和，并加上 f[x]f[x] 的初始值，得到最终的结果。

代码

CPP
#include <bits/stdc++.h> //万能头
using namespace std;
const int N = 500005;
int n, m;
int f[N], fa[N];

// 返回 x 的二进制表示中最低位的 1 所对应的值
int lowbit(int x) {
    return x & -x;
}

// 在树状数组的第 x 个位置加上 k
void add(int x, int k) {
    while (x <= n) {
        fa[x] += k;
        x += lowbit(x);
    }
}

// 查询树状数组中前 x 个元素的和
int search(int x) {
    int ans = 0;
    while (x != 0) {
        ans += fa[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> f[i];

    for (int i = 1, op, x, y, z; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            // 区间修改
            cin >> x >> y >> z;
            add(x, z);
            add(y + 1, -z);
        } else {
            // 单点查询
            cin >> x;
            cout << f[x] + search(x) << "\n";
        }
    }
}

复杂度分析：

时间复杂度： 每次区间修改和单点查询的时间复杂度均为 O(logn)O(log n) 。
总的时间复杂度为 O(mlogn)O(m log n)。
空间复杂度：树状数组 fafa 的空间复杂度为 O(n)O(n) 。

总结：

通过使用树状数组和差分的思想，我们可以高效地处理区间修改和单点查询操作。这种方法在时间复杂度和空间复杂度上都表现良好，适用于处理大规模数据的场景。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...