HDU4027 Can you answer these queries? 线段树

思路：http://www.cnblogs.com/gufeiyang/p/4182565.html

写写线段树

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5;
LL a[N<<2];
void build(int rt,int l,int r){
    if(l==r){
       scanf("%I64d",&a[rt]);
       return;
    }
    int m=(l+r)>>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    a[rt]=a[rt<<1]+a[rt<<1|1];
}
void modify(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y){
      if(a[rt]==r-l+1)return;
    }
    if(l==r){
       a[rt]=sqrt(1.0*a[rt]);
       return;
    }
    int m=(l+r)>>1;
    if(x<=m)modify(rt<<1,l,m,x,y);
    if(y>m)modify(rt<<1|1,m+1,r,x,y);
    a[rt]=a[rt<<1]+a[rt<<1|1];
}
LL ask(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y)return a[rt];
    LL ans=0;
    int m=(l+r)>>1;
    if(x<=m)ans+=ask(rt<<1,l,m,x,y);
    if(y>m)ans+=ask(rt<<1|1,m+1,r,x,y);
    return ans;
}
int main(){
    int n,cas=0;
    while(~scanf("%d",&n)){
        printf("Case #%d:
",++cas);
        build(1,1,n);
        int q;
        scanf("%d",&q);
        while(q--){
           int op,x,y;
           scanf("%d%d%d",&op,&x,&y);
           if(x>y)swap(x,y);
           if(op)printf("%I64d
",ask(1,1,n,x,y));
           else modify(1,1,n,x,y);
        }
        printf("
");
    }
    return 0;
}