树状数组

线段树似乎和树状数组有这不可告人的秘密。

近期看了线段树和树状数组。在我的大脑中 树状数组是特殊的一种线段树。

线段树我好久之前就写过文章了。可是用的太少每次都忘。

所以还是写看写几次就能记住，毕竟写一次有一次的收获嘛。

如今我们来说树状数组。

以下我来说一下我个人对一个问题的方法，学一个新东西。先来知道这个问题是来解决什么样的问题 。然后我们来看这种方法的思路，不要把问题想的太复杂。

我们就拿树状数组来举个样例吧。

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 就是求逆序数的问题了。我想后面我会写关于树状数组求逆序数的文章。

好了，感谢自己坚持 。