树状数组的学习（持续更新）

目录

树状数组

树状数组求逆序对

逆序对

树状数组

主要可以用来求前缀和，可支持单点修改。

优点是代码短，缺点是不好理解，不易容易看出

树状数组是用来简化线段树的，大部分的树状数组的题都可用线段树来解决，但是树状数组的常数小，代码简短写起来更快。

知识点关联

1. Lowbit

顾名思义求数在二进制中最后一个一的位置。

原理补码有关

代码 x&-x

主要部分

1.树状数组解释

树状数组和状态压缩有点类似，都是用二进制来表示每一位的数，在树状数组中，每个位置所代表数都是一段区间的前缀和，区间的长度是由这个数最后一位一所决定的

2.树状数组的插入

树状数组的插入不仅要改变自己，还有改变数组中所有包含该位置的数，因其是在二进制下的表现形式，所以包含该位置的所有数就是a+lowbit（a）

代码：

void down(int a,int n)

{

while(a<=n)

{

l[a]++;a+=(a&-a);

}

}

3.树状数组查询一个数之前的和

由前边可知，树状数组的每个位置都是代表了lowBi（t）长度的区间和，我们想要求前缀和只需要每次将前边求过的前缀和相加就好并减去lowbit

代码

int up(int a,int n)

{

int sum=0;

while(a)

{

sum+=l[a];  a-=(a&-a);

}

//cout<<sum<<"???";

return sum;

}

主要应用

树状数组求逆序对

前置知识

逆序对：大小相反即为逆序对

主要部分

给予我们一个数组，假设在这个数（a）出现之前已经存在x个数了，我们将这x个数分为两部分，一部分比a小，剩下的为另一部分。

那么我们就可以通过每次统计这个数中比它小的部分，然后用x-比他小的，就是这个数对最后逆序对答案的贡献度。

代码

for(int i=1;i<=n;i++)

   {

    int a;

    cin>>a;

    sum+=i-1-up(a-1,n);//注意存储的时候不包括输入的数

    down(a,n);

   // cout<<sum<<"???";

   }

最后

以上就是包容方盒为你收集整理的树状数组的学习（持续更新）的全部内容，希望文章能够帮你解决树状数组的学习（持续更新）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。