二叉索引树(binary indexed tree)
适用组别：提高组
难度系数：6
P3368
二叉索引树又叫树状数组，是一种用于高效处理对一个存储数字的列表进行更新及求前缀和的数据结构。
1、区间长度(lowbit(i))：
是i在二进制下，最低位的1之后的0构成的数值。
例如：
15的二进制是1111，最后一位是1，没有零，所以lowbit(15)就是1
12的二进制是1100，最低位的1后面有两个0，100在二进制下是4，所以区间长度lowbit(12)是4
2、前驱和后继
直接前驱：s[i]的直接前驱为s[i-lowbit(i)]，即s[i]左侧紧邻的子树的根。
直接后继：s[i]的直接后继为s[i+lowbit(i)]，即s[i]的父结点
前驱：s[i]左侧所有子树的根
后继：s[i]的所有祖先
某位置i的前缀和等于s[i]加上（i-lowbit(i)）位置的前缀和
例如：
sum[10]=s[10]+s[8]=11+36=47
sum[15]=s[15]+s[14]+s[12]+s[8]=66
3、lowbit计算
lowbit(i)=(-i)&i
例如：i=20, i(bit)=101100 -i=01011+1=01100
01100
&10100
——————-
00100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /**************************************************************** * Description: C++ implementation of Binary Indexed Tree * Author: Alex Li * Date: 2023-06-24 14:30:05 * LastEditTime: 2024-08-09 21:09:40 ****************************************************************/ #include <iostream> using namespace std; const int maxn=10001; int n, arr[maxn], s[maxn]; //arr是存放原始数据，s[]是树状数组 // Lowbit函数用于获取整数i的二进制表示中最低位的1所代表的值 int Lowbit(int i){ return (-i)&i; } //用于在树状数组中更新增加值 void Add(int i, int z){ for (; i <=n; i+=Lowbit(i)) s[i]+=z; } //用于计算从数组开头到索引i的前缀和 int prefixSum(int i){ int sum=0; for (; i>0; i-=Lowbit(i)) sum+=s[i]; return sum; } //用于计算索引j到i的区间和 int rangeSum(int i,int j){ return prefixSum(i)-prefixSum(j-1); } int main(){ int a,b; cin>>n;//输入数组的长度 for (int i = 1; i <=n; i++){ cin>>arr[i]; // 输入数组的元素 Add(i,arr[i]); // 更新树状数组 } cin>>a; cout<<prefixSum(a); cin>>a>>b; // a>b cout<<rangeSum(a,b)<<endl; return 0; } |
练习题：I8633