学步园

        两个月前用暴力穷举做这道题目，超时！一直不得其解，今天学了一下树状数组，刚刚用这个在线数据结构AC了这道题目。

       这道题目的ＵＲＬ：http://acm.nyist.net/JudgeOnline/problem.php?pid=116

　　树状数组的功能：查询一段区间的值的和。并且修改和查询的复杂度都是log(N)的。比起简单的暴力求和要快的多。

        我这里给出自己的代码给大家参考

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

const int Max = 1000000 + 10;

int c[Max]; //树状数组
int num; //数组大小 

//求value变量的二进制表示的最后一个1所在位的权值
int lowbit(int value)
{
	return (value & (value ^ (value - 1)));
}

//修改pos位及其所有祖先的值
void modify(int pos, int value)
{
	while(pos <= num)
	{
		c[pos] += value;
		pos += lowbit(pos);
	}
}

//求1到pos的和
int sum(int pos)
{
	int total = 0;
	while(pos > 0)
	{
		total += c[pos];
		pos -= lowbit(pos);
	}
	return total;
}

int main()
{
	int m, value; //
	char ins[10];
	int a, b;
	scanf("%d%d", &num, &m);
	
	memset(c, 0, sizeof(c)); //初始化
	for(int i=1; i<=num; i++)
	{
		scanf("%d", &value);
		modify(i, value);
	}
	
	for(int i=0; i<m; i++)
	{
		scanf("%s%d%d", ins, &a, &b);
		switch(ins[0])
		{
		case 'A':
			modify(a, b);
			break;
		case 'Q':
			int cnt = sum(b) - sum(a-1);
			printf("%d\n", cnt);
			break;
		}
	}
	system("pause");
	return 0;
}

，关于树状数组的知识大家可以百度百科一下。