模板建站服务公司,wordpress pckr,广州:推动优化防控措施落,深圳有哪些网站建设树状数组#xff08;Fenwick Tree#xff09;是一种用于维护数组前缀和的数据结构#xff0c;支持高效的单点更新和区间查询操作。它的查询和更新时间复杂度为 O ( log n ) O(\log n) O(logn)#xff0c;适用于需要频繁更新和查询的场景。
树状数组的基本操作
单点更…树状数组Fenwick Tree是一种用于维护数组前缀和的数据结构支持高效的单点更新和区间查询操作。它的查询和更新时间复杂度为 O ( log n ) O(\log n) O(logn)适用于需要频繁更新和查询的场景。
树状数组的基本操作
单点更新将数组中的某个元素增加一个值。前缀和查询查询数组从起点到某个位置的元素和。
树状数组的实现步骤
初始化创建一个大小为 (n1) 的数组 tree初始值为 0。单点更新更新数组中的某个元素并相应地更新树状数组。前缀和查询计算从起点到某个位置的元素和。
以区间和问题举例 我们有一个数组即图片中最下面一行的数组我们也可以理解为最下面一层是长度为1的区间倒数第二层是长度为2的区间然后是长度为4的区间以此类推并且区间不重叠。
这个图片展示出来的就是一颗线段树树状数组是线段树的升级版。我们发现每一个子树的右半部分可以省略不用。例如要查询[1,3]的区间和可以通过141而不用通过861因此我们可以优化这棵树得到 到了这里树状数组的组成结构基本就结束了但是这样组织后怎么确定节点之间的关系这就要用到lowbit这是一个十分巧妙的概念。 将剩下的元素组成一个数组后我们发现数组每一个位置索引对应的lowbit就代表了这个位置存储的区间长度。例如我们观察61这个数索引是16树状数组索引从1开始16的lowbit是1610000-10000代表61是区间长度为16的区间和即[1,16]同理3的索引是99的lowbit是11001-1代表9是区间长度为1 [9,9]的区间和。
查询是向前查询
有了这个概念后查询和更新就很明显了如果要查询区间[l,r]我们可以查询[0,r]-[0,l]查询方式是递归减去lowbit累计数组元素的和例如计算[1,3]我们先得到索引为3的数值1然后更新位置 3-lowbit(3)2然后从2开始得到142-lowbit(2)0结束递归结果为11415。
更新是向后更新
对于更新树状数组的元素我们需要修改每一个包含了这个元素的所有区间。 与查询不同修改需要向后修改。如果修改了索引为9的3我们需要修改9,10,12,16存储的内容。我们发现与查询相似可以通过lowbit来得到包含自己的更大的区间例如:9lowbit(9)10, 10lowbit(10)12, 12lowbit(12) 16因此我们同样使用递归直到索引到达数组长度上限。
区间异或问题
#includebits/stdc.husing 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;}}
}
