线段树基础题

1.单点修改裸题（HDU1754）

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2e+5;
int n,m,a[maxn];

struct tree{
    int l,r,v;
}trees[maxn<<2];

void buildtree(int s,int l,int r)
{
    trees[s].l=l,trees[s].r=r;
    if(l==r)
    {
        trees[s].v=a[l];
        return ;
    }
    int mid=l+r>>1;

    buildtree(s<<1,l,mid);
    buildtree(s<<1|1,mid+1,r);

    trees[s].v=max(trees[s<<1].v,trees[s<<1|1].v);
}

void update_point(int s,int a,int m)
{
    if(trees[s].l==a&&trees[s].r==a)
    {
        trees[s].v=m;
        return ;
    }
    int mid=trees[s].l+trees[s].r>>1;

    if(a<=mid)
        update_point(s<<1,a,m);
    if(a>mid)
        update_point(s<<1|1,a,m);

    trees[s].v=max(trees[s<<1].v,trees[s<<1|1].v);
}

int ask_interval(int s,int l,int r)
{
    if(trees[s].l==l&&trees[s].r==r)
        return trees[s].v;
    int mid=trees[s].l+trees[s].r>>1;

    if(r<=mid)
        return ask_interval(s<<1,l,r);
    if(l>mid)
        return ask_interval(s<<1|1,l,r);
    if(l<=mid&&r>mid)
        return max(ask_interval(s<<1,l,mid),ask_interval(s<<1|1,mid+1,r));

    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    while(cin>>n>>m){

        for(int i=1;i<=n;++i) cin>>a[i];
        buildtree(1,1,n);

        while(m--){
        char op;int c,d;
        cin>>op>>c>>d;
        if(op=='Q')
            cout<<ask_interval(1,c,d)<<endl;
        else
            update_point(1,c,d);
         }
    }

    return 0;
}

2.区间修改-非累加（HDU1698）

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int n,m;
typedef long long ll;
struct tree{
    int l,r,sum,lazy_tag;
}trees[maxn<<2];

void pushdown(int s)
{
    trees[s<<1].lazy_tag=trees[s].lazy_tag;
    trees[s<<1|1].lazy_tag=trees[s].lazy_tag;
    trees[s<<1].sum=trees[s].lazy_tag*(trees[s<<1].r-trees[s<<1].l+1);
    trees[s<<1|1].sum=trees[s].lazy_tag*(trees[s<<1|1].r-trees[s<<1|1].l+1);
    trees[s].lazy_tag=0;

}
void buildtree(int s,int l,int r)
{
    trees[s].l=l,trees[s].r=r;
    trees[s].lazy_tag=0;
    if(l==r)
    {
        trees[s].sum=1;
        return ;
    }
    int m=l+r>>1;
    buildtree(s<<1,l,m);
    buildtree(s<<1|1,m+1,r);

    trees[s].sum=trees[s<<1].sum+trees[s<<1|1].sum;
}

void update(int s,int l,int r,int value)
{
    if(l<=trees[s].l&&r>=trees[s].r)
    {
        trees[s].lazy_tag=value;//非累加是替换
        trees[s].sum=value*(trees[s].r-trees[s].l+1);
        return ;

    }

    if(trees[s].lazy_tag) pushdown(s);

    int m=trees[s].l+trees[s].r>>1;

    if(l<=m)
        update(s<<1,l,r,value);
    if(r>m)
        update(s<<1|1,l,r,value);

    trees[s].sum=trees[s<<1].sum+trees[s<<1|1].sum;
}
int ans;
void query(int s,int l,int r)
{

    if(trees[s].l>=l&&trees[s].r<=r)
    {
        ans+=trees[s].sum;
        return ;
    }
    if(trees[s].lazy_tag) pushdown(s);
    int m=trees[s].r+trees[s].l>>1;
    if(l<=m)
        query(s<<1,l,r);
    if(r>m)
        query(s<<1|1,l,r);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    for(int cas=1;cas<=T;++cas){
        ans=0;
        int n,q,x,y,value;
        cin>>n>>q;
        buildtree(1,1,n);
        while(q--){
            cin>>x>>y>>value;
            update(1,x,y,value);
        }
        query(1,1,n);
        cout<<"Case "<<cas<<": The total value of the hook is "<<ans<<"."<<endl;

    }
}