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
思路:基礎的線段樹模板直接套,作為自己線段樹做的第一道題,代碼紀念一下
#include#include #include #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std ; const int maxn = 555555 ; 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 m = (l+r)>>1 ; build(lson) ; build(rson) ; pushUp(rt) ; } void update(int p,int add,int l,int r,int rt) //更新操作 { if(l == r) { sum[rt]+=add ; return ; } int m = (l+r)>>1 ; if(p<=m) { update(p,add,lson) ; } else { update(p,add,rson) ; } pushUp(rt) ; } int query(int L,int R,int l,int r,int rt) //查詢操作,L,R代表查詢左右區間 { if(r<=R && L<=l) { return sum[rt] ; } int m = (l+r)>>1 ; int ret = 0 ; if(L <= m) { ret+=query(L,R,lson); } if(R>m) { ret+=query(L,R,rson) ; } return ret ; } int main() { int t,n ; while(scanf("%d",&t)!=EOF) { for(int k = 1 ;k<=t ;k++) { scanf("%d",&n) ; build(1,n,1) ; char op[10] ; printf("Case %d:\n",k) ; while(scanf("%s",op)) { if(op[0] == 'E') break ; int a,b ; 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) ; } } } return 0 ; }