http://acm.hdu.edu.cn/showproblem.php?pid=4027
題意：給一個數(shù)組序列， 數(shù)組長度為100000，現(xiàn)在有兩種操作， 一種操作是將某一個固定區(qū)間所有數(shù)開方（向下取整），另一種操作是詢問某個區(qū)間的所有數(shù)字之和。
題解：線段樹：單點更新，區(qū)間求和。注意一個可以優(yōu)化的地方：在query和update操作中，如果segTree[rt]==r-l+1，說明該區(qū)間內(nèi)所有數(shù)都為1，開方也是1,則不必遞歸下去了。

#include<stdio.h>
#include<cmath>
#include<algorithm>
#include <string.h>
using namespace std;
#define maxn 100010
typedef long long LL;
LL segTree[maxn<<2];
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%lld",&segTree[rt]);
        return;
    }
    int mid=l+((r-l)>>1);
    build(l,mid,rt<<1);
    build(mid+1,r,(rt<<1)|1);
    segTree[rt]=segTree[rt<<1]+segTree[(rt<<1)|1];
}
LL query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return segTree[rt];
    if(L<=l&&r<=R&&segTree[rt]==r-l+1) return r-l+1;
    int mid=l+((r-l)>>1);
    LL sum=0;
    if(mid>=L) sum=sum+query(L,R,l,mid,rt<<1);
    if(mid+1<=R) sum=sum+query(L,R,mid+1,r,(rt<<1)|1);
    return sum;
}
void update(int L,int R,int l,int r,int rt)
{
    if(l==r)
    {
        segTree[rt]=sqrt(segTree[rt]);
        return;
    }
    if(L<=l&&r<=R&&segTree[rt]==r-l+1) return;
    int mid=l+((r-l)>>1);
    if(L<=mid) update(L,R,l,mid,rt<<1);
    if(mid+1<=R) update(L,R,mid+1,r,(rt<<1)|1);
    segTree[rt]=segTree[rt<<1]+segTree[(rt<<1)|1];
}
int main()
{
    int n,m,L,R,op,cas=0;
    while(scanf("%d",&n)!=EOF)
    {
        build(1,n,1);
        printf("Case #%d:\n",++cas);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&op,&L,&R);
            if(L>R) swap(L,R);
            if(op)
            {
                printf("%lld\n",query(L,R,1,n,1));
            }
            else
            {
                update(L,R,1,n,1);
            }
        }
        printf("\n");
    }
}