IT评测·应用市场-qidao123.com

标题: 树状数组记录 [打印本页]

作者: 美食家大橙子 时间: 2024-9-9 04:32
标题: 树状数组记录
树状数组（Fenwick Tree）是一种用于维护数组前缀和的数据结构，支持高效的单点更新和区间查询操作。它的查询和更新时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)，实用于必要频繁更新和查询的场景。
树状数组的基本操作

单点更新：将数组中的某个元素增长一个值。
前缀和查询：查询数组从起点到某个位置的元素和。

树状数组的实现步骤

初始化：创建一个大小为 (n+1) 的数组 tree，初始值为 0。
单点更新：更新数组中的某个元素，并相应地更新树状数组。
前缀和查询：计算从起点到某个位置的元素和。

以区间和题目举例：

我们有一个数组，即图片中最下面一行的数组，我们也可以理解为，最下面一层是长度为1的区间，倒数第二层是长度为2的区间，然后是长度为4的区间，以此类推，并且区间不重叠。
这个图片展示出来的就是一颗线段树，树状数组是线段树的升级版。我们发现，每一个子树的右半部门可以省略不用。例如要查询[1,3]的区间和，可以通过14+1，而不用通过8+6+1，因此我们可以优化这棵树，得到：

到了这里，树状数组的构成结构基本就竣事了，但是如许组织后，怎么确定节点之间的关系？这就要用到lowbit，这是一个十分巧妙的概念。

将剩下的元素构成一个数组后，我们发现，数组每一个位置索引对应的lowbit，就代表了这个位置存储的区间长度。例如我们观察61这个数，索引是16（树状数组索引从1开始），16的lowbit是16（10000->10000），代表61是区间长度为16的区间和，即[1,16]，同理，3的索引是9，9的lowbit是1（1001->1），代表9是区间长度为1 [9,9]的区间和。
查询是向前查询
有了这个概念后，查询和更新就很明显了，假如要查询区间[l,r]，我们可以查询[0,r]-[0,l]，查询方式是：递归减去lowbit，累计数组元素的和，例如计算[1,3]，我们先得到索引为3的数值1，然后更新位置 3-lowbit(3)=2，然后从2开始得到14，2-lowbit(2)=0，竣事递归，效果为1+14=15。
更新是向后更新
对于更新树状数组的元素，我们必要修改每一个包含了这个元素的全部区间。
与查询差异，修改必要向后修改。假如修改了索引为9的3，我们必要修改9,10,12,16存储的内容。我们发现，与查询相似，可以通过+lowbit来得到包含自己的更大的区间，例如:9+lowbit(9)=10, 10+lowbit(10)=12, 12+lowbit(12) = 16，因此我们同样使用递归，直到索引到达数组长度上限。
区间异或题目

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t[300005];
int a[300005];
int n, q;
inline int lowbit(int x) {
return x & -x;
}
int get(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) {
res ^= t[i];
}
return res;
}
void add(int x, int y) {
for (int i = x; i <= n; i += lowbit(i)) {
t[i] ^= y;
}
}
int range_get(int l, int r) {
return get(r) ^ get(l - 1);
}
int main(){
cin >> n >> q;
for(int i = 1; i <= n; i++){
cin >> a[i];
add(i, a[i]);
}
while(q--){
int op, x, y;
cin >> op >> x >> y;
if(op == 1){
add(x, y);
}else{
cout << range_get(x, y) << endl;
}
}
}

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)