势能分析线段树是这样一个东西，对于某一些操作，不滋磁打标记，只能暴力更改但操作很少次以后就不会改变结果了（最常见的就是区间开根号），我们可以维护一些东西来表示这个区间是否会改变。
题意就是给长度为n的区间，然后有2种操作，一是l~r的每个数变为原数的开方，二是查询l~r区间的和，这样更新方式和一般的加减某个数不一样了，用不了懒标记，那么如果每次更新区间时都进行单点更新的话复杂度是1e5*1e5肯定是会超时的，所以这里就另外用了一个标记，用来标记该节点是否需要更新，通过这个标记就可以将更新的复杂度由1e5*1e5降低至7*1e5,这样就可以过了（2^64开7次就变成1了，所以可以认为这n个数对应的叶子节点最多也就更新7次，所有更新的总复杂度是7*n）。
另外这题和ccf的除法那题也是类似的，都是用了势能线段树的这个思想。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100010
#define ls rt*2
#define rs rt*2+1
struct node
{
int l,r;
ll sum;
bool tag;
}tree[4*maxn];
ll a[maxn];
void build(int l,int r,int rt)
{
tree[rt].l=l;
tree[rt].r=r;
if(l==r)
{
tree[rt].sum=a[l];
if(tree[rt].sum==0||tree[rt].sum==1)
tree[rt].tag=true;
else
tree[rt].tag=false;
return ;
}
int mid=(l+r)/2;
build(l,mid,ls);
build(mid+1,r,rs);
tree[rt].sum=tree[ls].sum+tree[rs].sum;
tree[rt].tag=tree[ls].tag&&tree[rs].tag;
}
void update(int l,int r,int rt)
{
if(tree[rt].tag) return ;
if(tree[rt].l==tree[rt].r)
{
tree[rt].sum=sqrt(tree[rt].sum);
if(tree[rt].sum==1)
{
tree[rt].tag=true;
}
return ;
}
int mid=(tree[rt].l+tree[rt].r)/2;
if(mid>=r)
{
update(l,r,ls);
}
else
if((mid+1)<=l)
update(l,r,rs);
else
{
update(l,r,ls);
update(l,r,rs);
}
tree[rt].sum=tree[ls].sum+tree[rs].sum;
tree[rt].tag=tree[ls].tag&&tree[rs].tag;
}
ll query(int l,int r,int rt)
{
if(tree[rt].l>=l&&tree[rt].r<=r)
{
return tree[rt].sum;
}
int mid=(tree[rt].l+tree[rt].r)/2;
ll ans=0;
if(mid>=r)
{
ans=query(l,r,ls);
}
else
if((mid+1)<=l)
ans=query(l,r,rs);
else
{
ans=query(l,r,ls);
ans+=query(l,r,rs);
}
return ans;
}
int main()
{
int n,m,mycase=0;
while(scanf("%d",&n)!=EOF)
{
mycase++;
printf("Case #%d:
",mycase);
for(int i=1;i<=n;i++)scanf("%lld",&(a[i]));
build(1,n,1);
scanf("%d",&m);
while(m--)
{
int op,l,r;
scanf("%d %d %d",&op,&l,&r);
if(l>r)
swap(l,r);
if(op==0)
{
update(l,r,1);
}
else
{
printf("%lld
",query(l,r,1));
}
}
printf("
");
}
return 0;
}