二叉索引树(树状数组)——讲解

写在前面

追随树神的脚步!然而树神写的PPT还是很良心的,很快就看懂了,题解也不错。

原理

然后树状数组是不需要建树的,它的树成分并没有线段树那么强,是通过一个特殊的Lowbit来建立起来的;

树状数组的实现方式是用一个c数组维护原来的数组a,

Lowbit讲解:

c[i]=sum(a[j]) i-lowbit(i)+1<=j<=i;

这里的 lowbit(i) 表示将i转换成二进制后的最右边的1到最后所形成的十进制的数。

例如 lowbit(6)=lowbit(110)2=(10)2=2

所以 c[6]=a[5]+a[6];

lowbit(4)=lowbit(100)2=(100)2=4

c[4]=a[1]+a[2]+a[3]+a[4]

lowbit[5]=lowbit(101) 2 =(1) 2=1;

c[5]=a[5]

Lowbit公式:

下面是重点!!!

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

公式原理:

上面这个公式是非常重要的,就是通过求出一个数的 Lowbit 将这些数据建立成一个树的,父子节点和线段树关系类似,都是通过某种固定的方式建立起来的。而 lowbit 的原理就是利用了计算机里面的反码和补码(这世界本来就是二进制的!)

我们都知道在计算机中数使用二进制存储的,int 是 4 字节,例如我们把5换成二进制。 5=00000000 00000000 00000000 00000101 这同时也是5的原码。 原码:一个正数,按照值大小转换成的二进制数;一个负数按照绝对值大小转换成的二进制数,然后最高位补1,称为原码。

那么-5的原码就是 -5=10000000 00000000 00000000 00000101 ,其中,最高位的1是符号位。 在计算机中储存一个数用的是补码的形式,要了解补码需要先知道什么是反码。 反码:正数的反码与原码相同,负数的反码为对该数的原码除符号位外各位取反 -5的反码就是: 11111111 11111111 11111111 11111010

再说补码:正数的补码与原码相同,负数的补码是这个数的反码+1 -5:11111111 11111111 11111111 11111010+1 = 11111111 11111111 11111111 11111011

那么我们利用这个公式 x&(-x) 的意义:

6&(-6):

6: 00000000 00000000 00000000 00000110

-6: 11111111 11111111 11111111 11111010

Ans: 00000000 00000000 00000000 00000010

所以说 lowbit(6) 的结果很明显就是2

节点i的父亲节点为i+lowbit(i) 若需改变a[i],则c[i]、c[i+lowbit(i)]、 c[i+lowbit(i)+lowbit(i+lowbit(i)]……一直加到上限,就是需要改变的c数组中的元素。

若需查询s[i],则 c[i]c[i-lowbit(i)]c[i-lowbit(i)-lowbit(i-lowbit(i))] ……就是需要累加的c数组中的元素。 这样我们就让复杂度优化到了 O(logn)

觉得不是太懂???继续往下看!

修改代码:

1
2
3
4
5
6
7
8
void Change(int x,int add)
{
while(x<=n)
{
c[x]+=add;
x+=Lowbit(x);
}
}

查询代码:

1
2
3
4
5
6
7
8
9
10
int Question(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x-=Lowbit(x);
}
return ans;
}

树状数组原理:

然后我再放上一张图QAQ

这个就是树状数组在记录的时候,c数组记录的东西,这个本身是一个数组,利用lowbit来建立一个像树一样的结构(上图),然后利用到就像是二分(二进制分)思想,然后不断分开,进行计算。

二进制真的是神奇啊!将十进制狠狠的踩到地上……

1 2 1 3 1 2 1 4 就像是树一样……

P1356求和

题目描述:

输入一个数列A1,A2….An(1<=N<=100000),在数列上进行M(1<=M<=100000)次操作,操作有以下两种:

  1. 格式为C I X,其中C为字符“C”,I和X(1<=I<=N,|X|<=10000)都是整数,表示把把a[I]改为X
  2. 格式为Q L R,其中Q为字符“Q”,L和R表示询问区间为L,R,表示询问A[L]+…+A[R]的值。

输入:

第一行输入N(1<=N<=100000),表述数列的长度; 接下来N行,每行一个整数(绝对值不超过10000)依次输入每个数; 接下来输入一个整数M(1<=M<=100000),表示操作数量,接下来M行,每行为C I X或者Q L R。

输出:

对于每个Q L R 的操作输出答案。

题解:

这道题就是一个模板题,我们进行查询,一个区间x到y的时候,我们就先查询y到1的累加和,然后减去x到1的累加和就好了,改变值的时候我们就按照树状数组的定义方法进行修改,所有覆盖到他的数组都需要修改的。

代码:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,a[400000],c[400000];
int b[400000],x,y;
char Question_or_Change;
inline int In_int()
{
int This=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') F=-F;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
This=(This<<1)+(This<<3)+ch-'0';
ch=getchar();
}
return This*F;
}
inline char In_char()
{
char ch=getchar();
while(ch<'A'||ch>'z') ch=getchar();
return ch;
}
inline int Lowbit(int x)
{ return (x&(-x)); }
int Question(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x-=Lowbit(x);
}
return ans;
}
void Change(int x,int add)
{
while(x<=n)
{
c[x]+=add;
x+=Lowbit(x);
}
}
int main()
{
n=In_int();
for(int i=1;i<=n;i++)
{
b[i]=In_int();
a[i]=a[i-1]+b[i];
c[i]=a[i]-a[i-Lowbit(i)];
}
m=In_int();
for(int i=1;i<=m;i++)
{
Question_or_Change=In_char();
x=In_int(); y=In_int();
if(Question_or_Change=='Q')
{
int First=Question(x-1);
int Second=Question(y);
cout<<Second-First<<endl;
}
if(Question_or_Change=='C')
{
Change(x,y-b[x]);
b[x]=y;
}
}
return 0;
}

关于树状数组

如果仅仅从能解决的问题范围上面考虑的话,明显是线段树数要强大很多,而且树状数组能解决的问题,线段树都可以解决的,刚刚我在看到这句话之后,去吧我以前写过的树状数组的题目全部都翻出来了,发现事实的确就是如此,那么学习树状数组的目的是什么呢?以后所有的题目全部都用线段树来解决不就可以了了吗。

但是作为高级数据结构,树状数组的代码非常简洁,有着极其巧妙的 Lowbit 操作,在空间复杂度上面优于线段树,更重要的是在解决多维度问题上面,树状数组的展开能力是非常强的,网上有一句话说:线段树擅长解决横向问题,树状数组擅长解决纵向问题。如果能用树状数组解决,就上树状数组。

最后树状数组和线段树的区别就是(来自知乎的一位朋友精辟的比喻)

树状数组是站着上厕所的,线段树是蹲着上厕所的……