HDU1166_最简单易学的线段树

题目链接题目大意：有N个工兵的营地，对于这些营地有三种操作。

(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;

要求快速的实现这三种操作。首先我们可以分析到的是，三种操作可以被归并为两种，也就是修改和查询。每个营地相当于一个点，也就是点修改，查询i到j营地，就是所谓的区间查询。点修改区间查询，查询的是区间的和。由于具有区间的可加性，所以我们采用线段树这种数据结构来维护。至于什么是线段树？线段树是一颗二叉树，每个非叶子节点都会有两个儿子，每个节点保存一区间的信息。线段树用到的是一种二分的思想，我们考虑一个数组。有n个元素，现在就来考虑这n个元素的和。我们将这些元素放在一颗二叉树上，怎么放？二分，不明白？OK，上图

。 HDU1166_最简单易学的线段树

我们用1-6生成一颗线段树。首先需要明确的是，节点里面存的值很重要，这个值就是需要维护的值。由于本题我们需要求和所有的元素，所以这里维护的就是区间和。根节点首先放置的就是1-6的和，也就是21，然后左儿子是（1+6）/2，所以左边就是1-3，节点保存的值就是6，有儿子就是4-6.也就是15，继续二分下去，那么我们可以将每一个元素更新到叶子节点上去。那么这个数据有什么好处呢，首先肯定是方便我们查询区间和，我们其实做了一个类似于预处理的操作，但是，这个不是简单的预处理，由于询问的区间并不能事先知道，所以你不能预处理掉所有的可能区间，但是我们这样的预处理，也就谁用一棵树来保存区间和，可以证明，所有的区间和都是可以通过这些树上的一些区间和累加起来。这也就是为什么大大的加速了查询的操作，再来看修改，修改一个区间，我们可以发现，其实任意一个元素都是在每一层里出现一次，也就是说我们修改的时候只需要每一层的这个元素所在的区间，可以证明这个操作实在log2（n)之内是可以完成的。所以点修改也是十分的迅速的。

在上边的分析中，其实我们隐含的已经使用了一些条件，而这些条件也正是使用线段树的一些显著的特征：符合区间的加法，大量的修改查询操作等。回到刚刚的题，其实我们使用线段树可以轻易的解决掉。下边给出代码，对于关键的地方给出解释。

#include <iostream>
#include<string>
using namespace std;
const int maxn = 50010;
int segTree[maxn * 4];  
//更新父节点操作，由于我们是使用的数组模拟的树，所以根节点和左右子树下标的关系是：
//根：k，左子树：2*k,右子树：2*k+1，
//使用位运算也就是：左：k<<1,右:k<<1|1.
void pushUp(int root)   
{
	segTree[root] = segTree[root * 2] + segTree[root * 2 + 1]; 
}
void build(int root, int left, int right)  
{
	if (left == right) 
	{
		cin >> segTree[root];
		return;
	}

	int mid = (left + right) / 2;

	//递归建立左子树和右子树
	build(root * 2, left, mid);
	build(root * 2 + 1, mid + 1, right);

	//每次更新父节点值.
     //很多初学者不是很明白这里为什么可以更新父节点，其实这里是递归的一个本质，递归是基于栈完成
 //的，所以当前操作完成后会返回到上一层，并且执行这个更新的操作，也就更新了父节点
	pushUp(root);
}

void update(int root, int p, int add, int left, int right) //单节点更新，p为待更新节点下标，add为需增加或减少的值
{
	if (left == right)  //找到单节点就更新
	{
		segTree[root] += add;
		return;
	}

	//二分查找指定节点
	int mid = (left + right) / 2;
	if (p <= mid)
	{
		update(root * 2, p, add, left, mid);
	}
	else
	{
		update(root * 2 + 1, p, add, mid + 1, right);
	}
	pushUp(root);
}
int query(int root, int q_left, int q_right, int now_left, int now_right)  //查询区间
{
	if (q_left <= now_left && q_right >= now_right)  //当前节点区间包含在查询区间内
	{
		return segTree[root];
	}

	int mid = (now_left + now_right) / 2;
	int sum = 0;
	if (q_left <= mid)
	{
		sum += query(root * 2, q_left, q_right, now_left, mid);
	}
	if (q_right > mid)
	{
		sum += query(root * 2 + 1, q_left, q_right, mid + 1, now_right);
	}
	return sum;
}
int main()
{
	ios::sync_with_stdio(false);   
	int t, n;
	string op;
	cin >> t;
	for (int i = 1; i <= t; i++)
	{
		cout << "Case " << i << ":" << endl;
		cin >> n;
		build(1, 1, n);
		while (cin >> op)
		{
			if (op[0] == 'E')
			{
				break;
			}
			int a, b;
			cin >> a >> b;
			if (op[0] == 'Q')   //询问
			{
				int ans = query(1, a, b, 1, n);
				cout << ans << endl;
			}
			else if (op[0] == 'S')  //减
			{
				update(1, a, -b, 1, n);
			}
			else if (op[0] == 'A')  //加
			{
				update(1, a, b, 1, n);
			}
		}
	}
	return 0;
}

HDU1166_最简单易学的线段树

相关推荐