树状数组(Binary Indexed Tree) 总结分析

无情 阅读:423 2020-10-19 15:34:56 评论:0

1.“树状数组”数据结构的一种应用

  对含有n个元素的数组(a[1],...,a[k],...,a[n]):

  (1)求出第i个到第j个元素的和,sum=a[i]+...+a[j]。

    进行j-i+1次加法,复杂度为O(j-i+1)

  (2)任意修改其中某个元素的值。

    使用数组下标可以直接定位修改,时间复杂度为O(1)

   对于同时支持上述两种操作的系统中,求和操作(1)求任意连续个数组元素和的平均时间复杂度为O(n),修改操作(2)时间复杂度是O(1)。如果系统中大量进行上述两种操作m次,其中执行操作(1)概率1/p,操作(2)概率1-1/p,则系统时间复杂度为:

  可以使用树状数组使得上述两种操作的时间复杂度为O(m*logn)

2.树状数组介绍

  核心思想:

    (1)树状数组中的每个元素是原数组中一个或者多个连续元素的和。

    (2)在进行连续求和操作a[1]+...+a[n]时,只需要将树状数组中某几个元素的和即可。时间复杂度为O(lgn)

    (3)在进行修改某个元素a[i]时,只需要修改树状数组中某几个元素的和即可。时间复杂度为O(lgn)

  下图就是一个树状数组的示意图:

  解释如下:

  1) a[]: 保存原始数据的数组。(操作(1)求其中连续多个数的和,操作(2)任意修改其中一个元素)

    e[]: 树状数组,其中的任意一个元素e[i]可能是一个或者多个a数组中元素的和。如e[2]=a[1]+a[2]; e[3]=a[3]; e[4]=a[1]+a[2]+a[3]+a[4]。 

  2) e[i]是几个a数组中的元素的和?

    如果数字 i 的二进制表示中末尾有k个连续的0,则e[i]是a数组中2^k个元素的和,则e[i]=a[i-2^k+1]+a[i-2^k+2]+...+a[i-1]+a[i]。

    如:4=100(2)  e[4]=a[1]+a[2]+a[3]+a[4];

      6=110(2)  e[6]=a[5]+a[6]

      7=111(2)  e[7]=a[7]

  3) 后继:可以理解为节点的父亲节点。离它最近的,且编号末位连续0比它多的就是的父亲,如e[2]是e[1]的后继;e[4]是e[2]的后继。

      如e[4] = e[2]+e[3]+a[4] = a[1]+a[2]+a[3]+a[4] ,e[2]、e[3]的后继就是e[4]。

      后继主要是用来计算e数组,将当前已经计算出的e[i]添加到他们后继中。

    前驱:节点前驱的编号即为比自己小的,最近的,最末连续0比自己多的节点。如e[7]的前驱是e[6],e[6]的前驱是e[4]。

        前驱主要是在计算连续和时,避免重复添加元素。

      如:Sum(7)=a[1]+...+a[7]=e[7]+e[6]+e[4]。(e[7]的前驱是e[6], e[6]的前驱是e[4])

    计算前驱与后继:

      lowbit(i) = ( (i-1) ^ i) & i ;

      节点e[i]的前驱为 e[ i - lowbit(i) ];

      节点e[i]的前驱为 e[ i + lowbit(i) ]

3.树状数组代码示例

 1 #include <iostream> 
 2 #include <stdio.h> 
 3  
 4 using namespace std; 
 5  
 6 int input(int*,int*,int);    ///输入数据 
 7 int calStageSum(int*,int);    ///计算树状数组 
 8 int getSum(int*,int);    ///求出前n个数字的和 
 9 int updataElement(int*,int*,int,int,int);    ///更新某一位置上的元素 
10  
11 int main (){ 
12     int n; 
13     int newValue; 
14     cout<<"Input the n(n>3) :"; 
15     cin>>n; 
16  
17     int *num = new int[n+1]; 
18     int *sum = new int[n+1]; 
19  
20     cout<<"Input "<<n<<" numbers"<<endl; 
21     input(num,sum,n); 
22     calStageSum(sum,n); 
23  
24     cout<<"The sum of first three number:"<<getSum(sum,3)<<endl; 
25  
26     cout<<"Update the 2nd number value:"; 
27     cin>>newValue; 
28     updataElement(sum,num,n,2,newValue); 
29  
30     cout<<"The sum of first three number:"<<getSum(sum,3)<<endl; 
31  
32     delete []num; 
33     delete []sum; 
34     return 0; 
35 } 
36  
37 int input(int* num,int *sum,int n){ 
38     for(int i=1;i<=n;i++){ 
39         cin>>num[i]; 
40         sum[i] = num[i]; 
41     } 
42     return 0; 
43 } 
44  
45 int calStageSum(int *sum,int n){ 
46     int lowbit; 
47     int par; 
48     for(int i=1;i<=n;i++){ 
49         lowbit = ((i-1)^i)&i; 
50         par = lowbit+i;   ///后继节点id 
51         if(par <= n){ 
52             sum[par] = sum[par] + sum[i]; 
53         } 
54     } 
55     return 0; 
56 } 
57  
58 int getSum(int* sum,int n){ 
59     int sumPreN = 0; 
60     int lowbit  = 0; 
61     while(n!=0){ 
62         sumPreN += sum[n]; 
63         lowbit = ((n-1)^n)&n; 
64         n = n - lowbit; ///前驱节点id 
65     } 
66     return sumPreN; 
67 } 
68  
69 int updataElement(int* sum,int *num,int n,int pos,int newvalue){ 
70     int lowbit = 0; 
71     int dis = newvalue - num[pos]; 
72     num[pos] = newvalue; 
73     sum[pos] = sum[pos]+dis; 
74  
75     while(true){ 
76         lowbit = ((pos-1)^pos)&pos; 
77         pos = pos + lowbit; ///后继节点id 
78         if(pos <= n){ 
79             sum[pos] = sum[pos]+dis; 
80         } 
81         else 
82             break; 
83     } 
84     return 0; 
85 }
View Code

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号