线段树+细节（BZOJ3211: 花神游历各国

题意

https://www.lydsy.com/JudgeOnline/problem.php?id=3211

?区间中每个数开根号，询问区间和。

?n ≤ 100000，m≤200000 ,data[i]非负且小于10^9

分析

首先，能修改，求动态区间和， 想到用线段树
之后，分析题目的细节：开根
一个数多开几次根号并向下取整之后，会变成 1或者0
而在变成1 或 0之后再开根号， 值不变
所以，我们维护区间和， 和每个区间是不是全为 0或1，若是，则开根后sum不变
这样在修改的时候就会快 ,直接暴力

思考后有需要的请参考

#include<cstdio>
#include<cmath>
using namespace std;
#define MAX 100000
#define ll long long

int n,m;
ll a[MAX];

struct node{
    ll sumv;
    int is;
}tr[MAX<<2];

void push_up(int o) { tr[o].sumv = tr[o<<1].sumv + tr[o<<1|1].sumv ; tr[o].is = tr[o<<1].is & tr[o<<1|1].is ;}
void build(int o, int l, int r) {
    if(l == r) {
        tr[o].sumv = a[l];
        tr[o].is = 0;
        if(a[l] == 0 || a[l] == 1) tr[o].is = 1;
        return ;
    }
    int mid = (l+r)>>1;
    build(o<<1, l, mid);
    build(o<<1|1, mid+1, r);
    push_up(o);
}

void update(int o, int l, int r, int ql, int qr) {
    if(tr[o].is == 1) return ;//提速 
    if(l == r) {//注意，这里是修改每个点 
        tr[o].sumv = (ll)sqrt(tr[o].sumv );
        if(tr[o].sumv == 0 || tr[o].sumv == 1) tr[o].is = 1;
        return ;
    }
    int mid = (l+r)>>1;
    if(ql <= mid) update(o<<1, l, mid, ql, qr);
    if(mid < qr) update(o<<1|1, mid+1, r, ql, qr);
    push_up(o); 
}

ll query(int o, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return tr[o].sumv ;
    int mid = (l+r)>>1;
    ll ans = 0;
    if(ql <= mid) ans += query(o<<1, l, mid, ql, qr);
    if(mid < qr) ans += query(o<<1|1, mid+1, r, ql, qr);
    return ans;
}

int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, 1, n);
    scanf("%d", &m);
    int x,l,r; 
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d",&x,&l,&r);
        if(x == 1) printf("%lld\n", query(1, 1, n, l, r) );
        else if(x == 2) update(1, 1, n, l, r);
    }
}

线段树+细节（BZOJ3211: 花神游历各国

原文：https://www.cnblogs.com/tyner/p/11254096.html