Luogu p4145 seven minutes of God created questions 2 / Huashen travels around the world

Line segment tree solution

Find the root of the interval , Because it doesn't exist $sqrt({\sum }_{i=1}^n{a}_i)={\sum }_{i=1}^{n}sqrt(a_i)$ Excellent nature of , So every interval modification should recurse to the leaf node , Can not make a lazy mark . Because the value of the parent node needs the value of the child node to determine , It is impossible to calculate at one time .

Feasibility explanation

The complexity of this recursive modification method to leaf nodes is explosive ？ It's better not to make achievements ？ It's not like that , For one $int$ Range of integers , Because each square root is rounded down , The number of square root is not greater than $6$ Times will make the value of this number 1, There is no need to prescribe any more . Then each number is at most square $6$ Time . So we can assign a value to each node $v$ , Represents the number of this interval $1$ . If this interval is 1 The number of is equal to the number of numbers in this interval , It means that the interval is full of $1$ , You do not need to perform the square root operation for this interval , Just go back .

Concrete realization

Look at the code .

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,m;
struct node{
    
	ll l,r,w,v;//w Interval sum ,v by 1 Quantity and sum 
}t[maxn<<2];
ll a[maxn];
inline void pushup(int k)
{
    // Update the data of the parent node at the same time 
	t[k].w=t[k<<1].w+t[k<<1|1].w;
	t[k].v=t[k<<1].v+t[k<<1|1].v;
}
inline void build(int k,int l,int r)
{
    
	t[k].l=l,t[k].r=r;
	if(l==r){
    
		t[k].w=a[l];
		t[k].v=(t[k].w==1)?1:0;// The initial judgment is whether there is 1
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
inline void update(int k,int l,int r)
{
    
	int x=t[k].l,y=t[k].r;
	if(t[k].v==y-x+1)return;// All sections are 1, No need to update , Go straight back to 
	if(x==y){
    // Must be updated to the leaf node 
		t[k].w=sqrt(t[k].w);
		t[k].v=(t[k].w==1)?1:0;
		return;
	}
	int mid=x+y>>1;
	if(l<=mid)update(k<<1,l,r);
	if(mid<r)update(k<<1|1,l,r);
	pushup(k);
}
inline ll query(int k,int l,int r)
{
    
	int x=t[k].l,y=t[k].r;
	if(l<=x&&y<=r)return t[k].w;
	int mid=x+y>>1;
	ll ans=0;
	if(l<=mid)ans+=query(k<<1,l,r);
	if(mid<r)ans+=query(k<<1|1,l,r);
	return ans;
}
int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	cin>>m;
	for(int i=1;i<=m;i++){
    
		int op,x,y;
		cin>>op>>x>>y;
		if(x>y){
    
			int tmp=x;x=y;y=tmp;
		}
		if(!op){
    
			update(1,x,y);
		}
		else{
    
			cout<<query(1,x,y)<<"\n";
		}
	} 
	return 0;
}