写在前面

追随树神的脚步！然而树神写的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 操作，在空间复杂度上面优于线段树，更重要的是在解决多维度问题上面，树状数组的展开能力是非常强的，网上有一句话说：线段树擅长解决横向问题，树状数组擅长解决纵向问题。如果能用树状数组解决，就上树状数组。

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

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