题解 | 区间根号与区间求和

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
using ll=long long;
//用数组实现区间根号与区间求和
vector<int> arr;
//定义节点结构体
struct Node{
    int l=0,r=0;
    ll sum=0;
    int maxVal=0;
    Node()=default;
    void setSumandValue(int s,int val){
        sum=s,maxVal=val;
    }
    void setLR(int tl,int tr){
        l=tl,r=tr;
    }
};
//定义二叉树的存储数组
vector<Node> tree;
//定义更新结构
void push_up(int node){
    tree[node].sum=tree[2*node].sum+tree[2*node+1].sum;
    tree[node].maxVal=tree[2*node].maxVal>tree[2*node+1].maxVal?tree[2*node].maxVal:tree[2*node+1].maxVal;
}

void buildTree(int node){
    int l=tree[node].l;
    int r=tree[node].r;
    if(l==r){
        tree[node].setSumandValue(arr[l], arr[l]);
        return;
    }
    int mid=(l+r)/2;
    tree[2*node].setLR(l, mid);
    buildTree(2*node);
    tree[2*node+1].setLR(mid+1, r);
    buildTree(2*node+1);
    //从底向上更新sum和maxVal
    push_up(node);
}
//区间修改操作
void update(int node,int ql,int qr){
    int l=tree[node].l;
    int r=tree[node].r;
    if(ql<=l && r<=qr){
        if(tree[node].maxVal<=1) return;
        else{
            if(l==r){
                tree[node].sum=sqrt(tree[node].sum);
                tree[node].maxVal=tree[node].sum;
            }else{
                update(2*node, ql, qr);
                update(2*node+1, ql, qr);
                push_up(node);
            }
        }
    }else{
        if(tree[2*node].r>=ql){
            update(2*node, ql, qr);
        }
        if(qr>=tree[2*node+1].l){
            update(2*node+1, ql, qr);
        }
        push_up(node);
    } 
    //假设区间为【1，8】，mid=4，左区间【1，4】，右【5，8】
    //查询区间【2，6】
}
//区间查询操作
ll query(int node,int ql,int qr){
    int l=tree[node].l;
    int r=tree[node].r;
    if(ql<=l && r<=qr){
        return tree[node].sum;
    }
    ll total=0;
    if(ql<=tree[2*node].r){
        total+=query(2*node, ql, qr);
    }
    if(qr>=tree[2*node+1].l){
        total+=query(2*node+1, ql, qr);
    }
    return total;
}
int main(){
    int n,q;
    cin>>n>>q;
    arr.resize(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    tree.resize(4*n+5);
    tree[1].setLR(1, n);
    buildTree(1);
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            update(1, l, r);
        }else{
            cout<<query(1, l, r)<<endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")