java怎莫做web网站百度网址大全手机版

树状数组（Fenwick Tree）是一种用于维护数组前缀和的数据结构，支持高效的单点更新和区间查询操作。它的查询和更新时间复杂度为 $O(\log n)$，适用于需要频繁更新和查询的场景。

树状数组的基本操作

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

树状数组的实现步骤

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

以区间和问题举例：

我们有一个数组，即图片中最下面一行的数组，我们也可以理解为，最下面一层是长度为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;}}
}