首页 > 其他 > 详细

HDU 1166 敌兵布阵 Segment Tree题解

时间:2014-06-20 12:34:36      阅读:397      评论:0      收藏:0      [点我收藏+]

本题是最基本的分段树操作了。或者一般叫线段树,不过好像和线段没什么关系,只是分段了。

不使用lazy标志,更新只是更新单点。

如果不使用分段树,那么更新时间效率只需要O(1),使用分段树更新效率就需要O(lgn)了。

但是不是用分段树,那么查询的时间效率是O(n),而分段树查询效率是O(lgn)

这就是amortize分摊了时间,而且lgn真的很快,数据不是非常巨大的时候,接近常数了。

故此本题需要使用分段树。

#include <cstdio>

class EnemyInfo
{
	static const int SIZE = 50001;
	int segTree[SIZE<<2];
	inline int lChild(int r) { return r<<1; }
	inline int rChild(int r) { return r<<1|1; }
	
	void pushUp(int root)
	{
		segTree[root] = segTree[lChild(root)] + segTree[rChild(root)];
	}

	void buildTree(int l, int r, int rt)
	{
		if (l == r)
		{
			scanf("%d", &segTree[rt]);
			return ;
		}

		int m = l + ((r-l)>>1);
		buildTree(l, m, lChild(rt));
		buildTree(m+1, r, rChild(rt));
		pushUp(rt);
	}

	void update(int addPoint, int addNum, int l, int r, int rt)
	{
		if (l == r)
		{
			segTree[rt] += addNum;
			return ;
		}

		int m = l + ((r-l)>>1);
		if (addPoint <= m) update(addPoint, addNum, l, m, lChild(rt));
		else update(addPoint, addNum, m+1, r, rChild(rt));
		pushUp(rt);
	}

	int query(const int L, const int R, int l, int r, int rt)
	{
		if (L <= l && r <= R) return segTree[rt];

		int m = l + ((r-l)>>1);
		int res = 0;
		if (L <= m) res += query(L, R, l, m, lChild(rt));
		if (R > m) res += query(L, R, m+1, r, rChild(rt));
		return res;
	}
public:
	EnemyInfo()
	{
		int T, n, a, b;
		scanf("%d",&T);
		for (int t = 1 ; t <= T ; t ++)
		{
			printf("Case %d:\n",t);
			scanf("%d",&n);
			buildTree(1 , n , 1);
			char op[6];
			while (scanf("%s",op) && op[0] != 'E')
			{
				scanf("%d%d",&a,&b);
				if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1));
				else if (op[0] == 'S') update(a , -b , 1 , n , 1);
				else update(a , b , 1 , n , 1);
			}
		}
	}
};



HDU 1166 敌兵布阵 Segment Tree题解,布布扣,bubuko.com

HDU 1166 敌兵布阵 Segment Tree题解

原文:http://blog.csdn.net/kenden23/article/details/28413777

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!