大家好，又见面了，我是全栈君。
线段树似乎和树状数组有这不可告人的秘密。
近期看了线段树和树状数组。在我的大脑中 树状数组是特殊的一种线段树。
线段树我好久之前就写过文章了。可是用的太少每次都忘。
所以还是写看写几次就能记住，毕竟写一次有一次的收获嘛。
如今我们来说树状数组。
以下我来说一下我个人对一个问题的方法，学一个新东西。先来知道这个问题是来解决什么样的问题 。然后我们来看这种方法的思路，不要把问题想的太复杂。
我们就拿树状数组来举个样例吧。
1，树状数组就是一种用log（n）的时间来改动和查询的数据结构。主要用来求数列的前n项和、一个区间的和等。
2，树状数组没什么复杂就是三个函数，有了这三个函数一切都攻克了。一个是用于计算的函数。一个改动函数，一个计算和的函数。就这么简单。
我们来看一下这个图先建立主要的想法
这样看可能有些复杂。
这里的A数组就是我们输入的数列数组、
c[1]存放的是A[1],
c[2]存放的是A[2]+A[1];
c[3]存放的是A[3];
c[4]存放的是A[4]+c[3]+c[2]也就是A[1]+A[2]+A[3]+A[4]；
从图中的连线就能看的出来。
我们先无论它是怎么计算出来的。
注意我们存数是从1開始的不是0.
以下我们来看一下如何来处理这样一个东西。
int lowbit(int n)
{
return n&(-n);
}
这个函数的用处就是让你计算用的。先无论，等我说完举个样例你就明确了。
void modify(int pos,int num)
{
while(pos<=n)
{
s[pos]+=num;
pos+=lowbit(pos);
}
}
这个函数是用来改动某个值的，就是将数组的 pos位置的数 加上 num。
这里用到了 上面的 lowbit函数了吧。
举个样例
将c【5】+1。 那么就须要调用modify（）函数了吧， 我们先将 c【5】+1，然后由于c【6】=A[5]+A[6]，所以c【6】也须要改动。然后是c【8】（假设对这个敌法个不是非常明确我们继续往下看），这样依次往后加入。
当中5是如何到的6 而6是如何到的8 呢就是用来lowbit（）这个函数。
以下这个函数是用来计算前n项的和了
int sum(int n)
{
int num=0;
while(n>0)
{
num+=s[n];
n-=lowbit(n);
}
return num;
}
我们这里再来举样例可能更easy理解。
1 求前8项的和 从图中能够看到c【8】直接或间接的连接了全部的数，那么c【8】就是前8项的和 lowbit（8）就是8 所以8-8=0停止循环。
2 求前7项的和 从图中看出c【7】仅仅存储可A[7]的值那么它须要再加前6项的值，lowbit（7）=1,7-1=6。那么跳到了6 的位置。c【6】的值A[5]+A[6]，我们加完了c【6】之后还须要加前4项的和。这时lowbit（6）=2，那么6-2=4，我们再加上c【4】的值，我们从图中也可已看出。c[4]存放的是A[4]+c[3]+c[2]也就是A[1]+A[2]+A[3]+A[4]；
这样我们就加完了。
应该可以明确吧。
我自己測试的完整的样例。
#include<iostream>
using namespace std;
int s[10000];
int n;
int lowbit(int n)
{
return n&(-n);
}
void modify(int pos,int num)
{
while(pos<=n)
{
s[pos]+=num;
pos+=lowbit(pos);
}
}
int sum(int n)
{
int num=0;
while(n>0)
{
num+=s[n];
n-=lowbit(n);
}
return num;
}
int main()
{
int x;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
modify(i,x);
}
int m;
while(cin>>m)
{
cout<<sum(m)<<endl;
}
}
好了树状数组介绍完了。我们来看一下能做的题。
1是单点更新求区间的值。
也就是中途更新单的点的值。
这样仅仅是调用modif（）函数即可了。
2是区间更新单点求值。我猜是这样一个题，在1-n上图色，看某个位置涂了几次。每次涂i-j。这样我们能够把数组初试话为0，假设这次图的是i-j的话，我们就调用modify（i，1），和modify（j，-1） 这样是有点巧妙。
3 就是求逆序数的问题了。我想后面我会写关于树状数组求逆序数的文章。
好了，感谢自己坚持 。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116480.html原文链接：https://javaforall.net
