学步园

      以前听一个同学提到过线段树，感觉很神奇，这次自己用线段树AC了一道题目，并没有想象当中的那么难。二分思想在线段树中的作用毋庸置疑！

      这是这道题的超链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166

      原理不解释，废话不多说。我看了几次线段树的理论知识，都没有什么直观的感觉。还是写代码解决实际问题才让我对线段树有了更深刻的认识。贴上我的代码，和大家分享。

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

const int Max = 50000 + 10;

struct Node
{
	int left, right;
	int count;
};

Node st[Max * 6]; //线段树 ，乘以4或3的时候就Access-violation, 报不清楚这是为什么。

//建树
void buildTree(int curNode, int left, int right)
{
	st[curNode].left = left;
	st[curNode].right = right;
	st[curNode].count = 0;

	if(left == right) return ;
	buildTree(curNode * 2, left, (left + right)/2);
	buildTree(curNode * 2 + 1, (left + right) / 2 + 1, right);
}

//更新结点值
void update(int curNode, int seq, int cnt)
{
	if(seq <= st[curNode].right && seq >= st[curNode].left)
	{
		st[curNode].count += cnt;

		update(curNode * 2, seq, cnt);
		update(curNode * 2 + 1, seq, cnt);
	}
}

//借助全局变量统计线段值
int total;
void sum(int curNode, int left, int right)
{
	int mid = (st[curNode].left + st[curNode].right) / 2; //左子区间的右端点
	if(st[curNode].left == left && st[curNode].right == right)
	{
		total += st[curNode].count;
	}
	else if(right <= mid) sum(curNode * 2, left, right); //所求线段全部落在左子区间
	else if(left > mid) sum(curNode * 2 + 1, left, right); //所求线段全部落在右子区间
	else //分治求解
	{
		sum(curNode*2, left, mid);
		sum(curNode*2+1, mid+1, right);
	}
}

int main()
{
	int cases, num, perNum;
	char ins[10];
	int a, b;

	cin >> cases;
	for(int c=1; c<=cases; c++)
	{
		scanf("%d", &num);
		memset(st, 0, sizeof(st));
		buildTree(1, 1, num);

		for(int i=1; i<=num; i++)
		{
			scanf("%d", &perNum);
			update(1, i, perNum);
		}

		printf("Case %d:\n", c);
		bool flag = true;
		while(flag)
		{
			scanf("%s", ins);
			switch(ins[0])
			{
			case 'Q':
				total = 0;
				scanf("%d%d", &a, &b);
				sum(1, a, b);
				printf("%d\n", total);
				break;
			case 'A':
				scanf("%d%d", &a, &b);
				update(1, a, b);
				break;
			case 'S':
				scanf("%d%d", &a, &b);
				b = -b;
				update(1, a, b);
				break;
			case 'E':
				flag = false;
				break;
			}
		}
	}
	system("pause");
	return 0;
}