题目地址： pid=1166">HDU 1166
听说胡浩版的线段树挺有名的。
于是就拜訪了一下他的博客。详情戳这里。于是就全然仿照着胡浩大牛的风格写的代码。
至于原理。鹏鹏学长已经讲的再清晰只是了。
我就在以下的代码凝视中将原理说明一下吧。来纪念第一发线段树。
以下是代码+凝视。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <stack>
using namespace std;
#define lson l, mid, rt<<1//直接定义子节点，由于每次都要用到，所以直接定义一个非常方便
#define rson mid+1, r, rt<<1 | 1
const int MAXN=51000;
int sum[MAXN<<2];
void PushUP(int rt)//向上更新父节点的值
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l, int r, int rt)//建立二叉树
{
if(l==r)//已经到达最底端的叶子节点，即单点，直接输入该值
{
scanf("%d",&sum[rt]);
return ;
}
int mid=(l+r)>>1;
build(lson);//向左子节点继续建立二叉树
build(rson);//向右子节点继续建立二叉树
PushUP(rt);//所有建立完后向上更新父节点的值
}
void update(int p, int x, int l, int r, int rt)//单点改动
{
if(l==r)//说明已经到了最底端的叶子节点，已经是单点了，能够直接改动该值
{
sum[rt]+=x;
return ;
}
int mid=(l+r)>>1;
if(p<=mid) update(p,x,lson);//假设要改动的值在这个区间左边，就进入左子节点继续寻找
else update(p,x,rson);//假设要改动的值在这个区间右边，就进入右子节点继续寻找
PushUP(rt);//改动完后。仍然要向上更新父节点的值
}
int query(int ll, int rr, int l, int r, int rt)//区间查询
{
if(ll<=l&&rr>=r)//假设要查询的区间全然覆盖了该子节点。直接返回该子节点的值
return sum[rt];
int mid=(l+r)>>1;
int ans=0;
if(ll<=mid) ans+=query(ll,rr,lson);//假设在该子节点左边另一部分要查询的区间。就去左子树继续查询
if(rr>mid) ans+=query(ll,rr,rson);//假设在该子节点右边另一部分要查询的区间，就去右子树继续查询
return ans;
}
int main()
{
int t, n, i, a, b, ans, num=0;
char s[20];
scanf("%d",&t);
while(t--)
{
num++;
printf("Case %d:\n",num);
memset(sum,0,sizeof(sum));
scanf("%d",&n);
build(1,n,1);//建立
/*for(i=1;i<=25;i++)
{
printf("%d %d\n",i,sum[i]);
}*/
getchar();
while(scanf("%s",s))
{
if(s[0]=='E') break;
if(!strcmp(s,"Add"))
{
scanf("%d%d",&a,&b);
update(a,b,1,n,1);//改动
}
else if(!strcmp(s,"Sub"))
{
scanf("%d%d",&a,&b);
update(a,-b,1,n,1); //改动
}
else
{
scanf("%d%d",&a,&b);
ans=query(a,b,1,n,1);//查询
printf("%d\n",ans);
}
}
}
return 0;
}