1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

Case 1:
6
33
59

我是根据挑战设计提供的线段树做的。

这是一个完美二叉树，树的样子是这样的。

图上的数字是数组下标。

                0

         1              2

   3      4         5         6

7   8  9 10  11 12 13 14

线段树做法：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>

const int MAX_N = 500000;
int pos;

int dat[MAX_N * 2 + 10000];//我数组开小了，WA了几次

using namespace std;


void update(int k)//更新
{
	while (k>0)
	{
		k = (k - 1) / 2;
		dat[k] = dat[2 * k + 1] + dat[2 * k + 2];
	}
}

void adda(int i, int j)//+
{
	dat[i] += j;
	update(i);
}
void suba(int i, int j)//-
{
	dat[i] -= j;
	update(i);
}

//求[a,b)之间的和
//k 是节点编号， l和r表示对应[l,r)区间
int querya(int a, int b,int k,int l,int r)
{
	int ans=0;
	//[a,b)和[l,r)不相交
	if (r <= a || b <= l)return 0;
	//[a,b)完全包含[l,r)
	if (a <= l&&r <= b)return dat[k];
	else 
	{
		//左边的和+右边的和
		ans += querya(a, b, k * 2 + 1, l, (l + r) / 2);
		ans += querya(a, b, k * 2 + 2, (l + r) / 2,r );
		return ans;
	}

}

int main()
{
	int t;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cout << "Case " << i+1 << ":" << endl;
		int n,a,b;
		string s;
		pos = 1;
		cin >> n;
		while (pos<n)//找到最后一层的节点数
		{
			pos *= 2;
		}
		memset(dat, 0, sizeof(dat));//初始化
		for (int j = 0; j < n; j++)
		{
			cin >> dat[j + pos-1];
			update(j + pos - 1);
		}
		while (cin >> s) 
		{
			if (s == "Add") { cin >> a >> b; a--; adda(a + pos - 1, b); }
			//所给的数据a是从1开始的，而树是从0开始的，所以要a--
			//最后一层的叶子节点的编号是从pos-1开始的。
			else if (s == "Sub") { cin >> a >> b; a--; suba(a + pos - 1, b); }
			else if (s == "Query") 
			{ 
				cin >> a >> b;
				a--;
				cout<<querya(a, b, 0, 0, pos)<<endl;
			}
			else if (s == "End")break;
		}
	}
	return 0;
}

//节点从1开始，从0开始会死循环

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>

const int MAX_N = 50100;

int bit[MAX_N];
int n;
using namespace std;

int sum(int i)//求(0，i]的和
{
	int s = 0;
	while (i>0)
	{
		s += bit[i];
		i -= i&-i;
	}
	return s;
}

void add(int i, int x)//向i节点的值加x
{
	while (i<=n)
	{
		bit[i] += x;
		i += i&-i;
	}
}

void sub(int i, int x)
{
	while (i <= n)
	{
		bit[i] -= x;
		i += i&-i;
	}
}


int main()
{
	int t;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cout << "Case " << i+1 << ":" << endl;
		int a,b;
		string s;
		cin >> n;
		memset(bit, 0, sizeof(bit));//初始化
		for (int j = 1; j <= n; j++)
		{
			int x;
			cin >> x;
			add(j, x);
		}
		while (cin >> s) 
		{
			if (s == "Add") { cin >> a >> b; add(a, b); }
			else if (s == "Sub") { cin >> a >> b;  sub(a , b); }
			else if (s == "Query") 
			{ 
				cin >> a >> b;
				a--;//[a,b]的值等于(0,b]-(0,a-1)的值
				cout<<sum(b)-sum(a)<<endl;
			}
			else if (s == "End")break;
		}
	}
	return 0;
}

最后

以上就是漂亮绿茶为你收集整理的HDOJ 1166 敌兵布阵 （区间求和）（线段树）（树状数组）敌兵布阵的全部内容，希望文章能够帮你解决HDOJ 1166 敌兵布阵 （区间求和）（线段树）（树状数组）敌兵布阵所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。