773
HDU 1166 線段樹單點更新
第一行一個整數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條命令
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 50005
using namespace std;
int num[N];
struct Tree
{
int l; //左端點
int r; //右端點
int sum; //總數
} tree[N*4]; // 總線段的長度為N，開數組的話一般開到N 的四倍
void build(int root,int l,int r) // root表示根節點 ，他的區間範圍【l,r】
{
tree[root].l=l;
tree[root].r=r;
if(tree[root].l==tree[root].r) // 當左右端點相等時就是葉子節點
{
tree[root].sum=num[l]; // 賦除值
return; // 遞歸出口
}
int mid=(l+r)/2;
build(root<<1,l,mid); // k<<1相等於k*2 即是他的左孩子
build(root<<1|1,mid+1,r); // k<<1|1 相當於k*2+1 ,即是他的右孩子
tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; // 父親的sum = 左孩子的sum + 右孩子的sum
}
void update(int root,int pos,int val) // root是根節點，pos，val表示：我們要跟新在pos點出的值更新為val
{
if(tree[root].l==tree[root].r) // 如果是葉子節點，即是pos對應的位置
{
tree[root].sum=val; // 更新操作
return; // 遞歸出口
}
int mid=(tree[root].l + tree[root].r)/2;
if(pos<=mid) // 如果pos點是在root對應的左孩子的話，就調用update(k<<1,pos,val); 在左孩子裏找
update(root<<1,pos,val);
else
update(root<<1|1,pos,val);
tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; // 父親的sum = 左孩子的sum + 右孩子的sum
}
int query(int root,int L,int R) // root表示根節點，[L,R]表示要查詢的區間
{
if(L<=tree[root].l&&R>=tree[root].r) // [L,R]要查詢的區間 包含root節點表示的區間 直接返回root節點的sum值
return tree[root].sum;
int mid=(tree[root].l + tree[root].r)/2,ret=0;
if(L<=mid) ret+=query(root<<1,L,R); // 查詢root節點的左孩子
if(R>mid) ret+=query(root<<1|1,L,R); // 查詢root節點的右孩子
return ret; // 返回
}
int main()
{
int t,n,ca=0;
char s[10];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&num[i]);
build(1,1,n);
printf("Case %d:\n",++ca);
while(scanf("%s",s),s[0]!='E')
{
int a,b;
scanf("%d%d",&a,&b);
if(s[0]=='Q')
{
if(a>b)
swap(a,b);
printf("%d\n",query(1,a,b));
}
if(s[0]=='A')
num[a]+=b,update(1,a,num[a]);
if(s[0]=='S')
num[a]-=b,update(1,a,num[a]);
}
}
return 0;
}
最後更新：2017-04-03 18:51:56