二叉索引树(binary indexed tree)

适用组别:提高组
难度系数:6

二叉索引树又叫树状数组,是一种用于高效处理对一个存储数字的列表进行更新及求前缀和的数据结构。



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
/**************************************************************** 
 * Description: C++ implementation of Binary Indexed tree
 * Author: Alex Li
 * Date: 2023-06-24 14:30:05
 * LastEditTime: 2023-06-24 15:12:34
****************************************************************/
#include <iostream>
using namespace std;

const int maxn=10001;
int n, arr[maxn], s[maxn];  //arr是存放原始数据,s[]是树状数组

int Lowbit(int i){
    return (-i)&i;
}

void Add(int i, int z){
     for (; i <=n; i+=Lowbit(i)) s[i]+=z;
}

//求前缀和
int prefixSum(int i){
    int sum=0;
    for (; i>0; i-=Lowbit(i)) sum+=s[i];
return sum;
}

//求区间和
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;
    
}
Scroll to Top