专题七：线段树 / 数据结构进阶 / 线段树
C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:”你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说：”我知错了。。。”但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.

Input

第一行一个整数T，表示有T组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(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 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令
Output

对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
Sample Input

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

Sample Output

Case 1:
6
33
59
  • 题意：
    • 实现单点增加、单点减少以及区间和查询
  • 题解：
    • 单点增加减少以及区间和可以用树状数组或者线段树实现，本题中树状数组时间与空间的效率均高于线段树，但是线段树是更为一般的实现方方法
  • 树状数组代码
  • //#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan_d(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int maxn = 1e6+10;
int c[maxn];
int a[maxn];
int n;
int ask(int x) {
	int ans=0;
	for(; x ; x -= x&-x)ans+=c[x];
	return ans;
}
void add(int x,int y) {
	for(; x<=n; x+= x&-x)c[x]+=y;
}
string cmd;
int main() {
	int t;
	scan_d(t);
	rep(w,1,t) {
		printf("Case %d:\n", w);
		scan_d(n);
		CLR(c);
		rep(i,1,n)scan_d(a[i]),add(i,a[i]);
		while(cin>>cmd) {
			int x,y;
			if(cmd[0]=='E')break;
			else {
				scan_d(x);
				scan_d(y);
				if(cmd[0]=='A') {
					add(x,y);
				} else if(cmd[0]=='S') {
					add(x,-y);
				} else {
					printf("%d\n", ask(y)-ask(x-1));
				}
			}
		}
	}
	return 0;
}
  • 线段树代码
  • //#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int maxn=1e6+10;

int a[maxn];
struct SegmentTree {
	int l,r;
	ll sum;
} t[maxn * 4];
void build(int p,int l,int r) { //build(1，1，n) 1为根节点
	t[p].l=l,t[p].r=r;
	if(l==r) {
		t[p].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void change(int p,int x,int v) { //change(1,x,v) 1为根节点
	if(t[p].l==t[p].r) {
        t[p].sum+=v;
		return ;
	}
	int mid=(t[p].l+t[p].r)/2;
	if(x<=mid)change(p*2,x,v);
	else change(p*2+1,x,v);
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
int ask(int p, int l, int r) {
	if (t[p].l >= l && t[p].r <= r)
		return t[p].sum;
	int sum=0;
	int mid = (t[p].l + t[p].r) / 2;
	if (l <= mid) {
		sum += ask(2 * p, l, r);
	}
	if (r > mid) {
		sum += ask(2 * p+1, l, r);
	}
	return sum;
}
string cmd;
int main() {
	int t,n;
	scan(t);
	rep(w,1,t) {
		printf("Case %d:\n", w);
		scan(n);
		rep(i,1,n)scan(a[i]);
		build(1,1,n);
		while(cin>>cmd) {
			int x,y;
			if(cmd[0]=='E')break;
			else {
				scan(x);
				scan(y);
				if(cmd[0]=='A') {
					change(1,x,y);
				} else if(cmd[0]=='S') {
					change(1,x,-y);
				} else {
					printf("%d\n", ask(1,x,y));
				}
			}
		}
	}
	return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注