基层建设网站,asp网站制作教程,国外服务器地址ip,做吉祥物的网站一.介绍 树状数组#xff08;Fenwick Tree#xff09;#xff0c;也称为二叉索引树#xff08;Binary Indexed Tree#xff0c;BIT#xff09;#xff0c;是一种用于高效处理动态数组前缀和的数据结构。它可以在O(log n)的时间复杂度内完成单点更新和区间查询操作。
树…一.介绍 树状数组Fenwick Tree也称为二叉索引树Binary Indexed TreeBIT是一种用于高效处理动态数组前缀和的数据结构。它可以在O(log n)的时间复杂度内完成单点更新和区间查询操作。
树状数组的主要应用是计算数组的前缀和。它通过将数组元素按照二进制表示的索引进行组织使得每个节点存储一定范围内的元素的和。通过利用二进制的特性树状数组可以高效地进行更新和查询操作。
树状数组的基本操作包括
单点更新Update将指定位置的元素值增加或减少一个给定的增量。区间查询Query计算指定区间内的元素和。
树状数组的构建过程如下
初始化一个长度为n的数组并将所有元素初始化为0。对于每个位置i将原始数组中的元素依次加到树状数组中同时更新相关节点的值。
树状数组的更新操作可以通过不断将当前位置的索引加上其最低位的1来实现。查询操作可以通过不断将当前位置的索引减去其最低位的1来实现。
树状数组的优点是实现简单、空间效率高并且支持高效的单点更新和区间查询操作。它在解决一些与前缀和相关的问题时非常有用比如计算逆序对、求解逆序数等。 二.详细讲解
1建树
若我们原数组为{123456789}
我们不妨可以这样加快区间合计算速度。 当我们求
c[1-9]c[1-8]c[9]
c[1-8]c[1-8]
c[1-7]c[1-4][5-6]c[7]
c[1-6]c[1-4]c[5-6]
c[1-5]c[1-4]c[5]
.........
这样的话我们修改一个单值只需要再修改它的父节点即可。
但我们再仔细看看会发现在求c[1-?]数组时都不需要用到右子树。
因为是奇数加上即可是偶数直接是父节点根本不需要右子树。我们优化掉。
于是树就是这样了 一棵树没了右子树自然节点就从O(n)--O(logn)
只也就算修改值只需要O(logn)的由来。
2建立/修改c数组
我们可以实现树了这里就可以用代码来实现。
因为是树所以可以使用二进制辅助。
一个父节点有多少左子节点呢其实就是它数组下标值的位权值。
位权值就是x(-x)求得。 位权值就是c数组包含的原数组元素的个数。
所以c[8]有a数组的8个元素即 c[8]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8];
所以c[6]有a数组的2个元素即 a[5]a[6];
总结c[x]有a数组的x(-x)个元素即c[x] a[x-lowbit(x)1]....a[x];
注意的是修改就要一次修改彻底所以添加/修改就要修改它所以的父节点
一个数x它的父节点就是x(x(-x));
修改元素的函数如下
void update(int x,int y){ //下标 值 for(;xn;x(x(-x))) {c[x]y;}
}
3查询区间
查询区间其实就是修改区间的逆运算。 就是累加它的子节点查询函数为
int fun(int x){ //return [1,x]int ans0;while(x){ansc[x];x-(x(-x));}return ans;
} 但这只能查询1-x啊x-y怎么办
求fun(y)-fun(x-1)不就行了嘛。
即a[3-8]a[1-8]-a[1-2]; 三.模板题
P3374 【模板】树状数组 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述 有n个整数可能会有两种操作: 1.将某一个数加上x;2.求出某区间数的和。 输入要求第一行包含两个整数N、M分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数其中第i个数字表示数列第i项的初始值。 接下来M行每行包含3个整数表示一个操作具体如下 操作1: 格式:1x k将第x个数加上k格式:2xy 操作2:输出区间[x,y]内每个数的和 样例输入 5 5 1 5 4 2 3 1 1 3 2 2 5 1 3 -1 1 4 2 2 1 4 样例输出 14 16 四 .参考代码
#includebits/stdc.h
#define maxn 500005
using namespace std;
int n,m;
int a[maxn]; //原数组
int c[maxn]; //树状树状
void update(int x,int y){ //下标 值 for(;xn;x(x(-x))) {c[x]y;}
}
int fun(int x){ //return [1,x]int ans0;while(x){ansc[x];x-(x(-x));}return ans;
}
int main(){scanf(%d%d,n,m);for(int i1;in;i){cina[i];update(i,a[i]); //建立树状数组 } while(m--){int op,x,y;scanf(%d%d%d,op,x,y);if(op1){update(x,y);}else{ //[3,7][1,7]-[1,2]coutfun(y)-fun(x-1)endl;}}return 0;
}
