【模闆】線段樹單點修改

• 基本介紹
• 模闆題目
• 代碼實作

基本介紹

在求區間最值的基礎上加了一個單點修改 也就是下面代碼中的update函數 主要通過不斷二分區間往下找左右子區間 直到一個子區間隻包括一個節點 直接改變這個節點的值并改變所有與這個點相關的父親節點 (摘自戰友Jiang.S部落格)

模闆題目

題目描述

給出N個數，兩種操作：

1、C x y：修改第x個數的值為y；

2、P x y：求第x到第y個的最大值，注：x未必比y小

輸入輸出格式

輸入格式：

第一行輸入N和M,N表示有N個數（N<=200000,M<5000），M表示有M個操作

下來N個數

然後是M個操作。

輸出格式：

遇到P操作的時候，輸出結果。

輸入輸出樣例

輸入樣例：

5 6

1 2 3 4 5

P 1 5

C 3 6

P 3 4

P 4 5

C 2 9

P 1 5

輸出樣例：

5

6

5

9

代碼實作

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<string>

    using namespace std;
    #define in = read()
    typedef long long ll;
    const ll size =  + ;

        #define left (rt<<1)
        #define right (rt<<1|1)
        #define mid ((l + r)>>1)
        #define lson l,mid,left
        #define rson mid + 1,r,right
        #define len (r - l + 1)

            ll n,m;
            ll tree[size];

inline ll read(){
        ll num =  , f = ;   char ch = getchar();

        while(!isdigit(ch)){
                if(ch == '-')   f = -;
                ch = getchar();
        }

        while(isdigit(ch)){
                num = num* + ch - '0';
                ch = getchar();
        }

        return num*f;
}

inline void pushup1(ll rt){   tree[rt] = max(tree[left] , tree[right]);}

void buildtree(ll l, ll r, ll rt){
        if(l == r){   tree[rt] in;      return;}
        buildtree(lson);    buildtree(rson);    pushup1(rt);
}

ll query(ll from,ll to,ll l,ll r,ll rt){
        if(from <= l && to >= r)    return tree[rt];
        ll ans = ;
        if(from <= mid)   ans = max(ans , query(from,to,lson));
        if(to > mid)    ans = max(ans , query(from,to,rson));
        return ans;
}

void update(ll num,ll dis,ll l,ll r,ll rt){
        if(l == r){   tree[rt] = dis;    return;}
        if(num <= mid)    update(num,dis,lson);
        else    update(num,dis,rson);
        pushup1(rt);
}

int main(){
        n in;   m in;
        buildtree(,n,);

        for(int i=;i<=m;i++){
                string s;    cin>>s;
                ll x,y;   x in;   y in;
                if(s[] == 'P'){
                        if(x <= y) 
                                printf("%lld\n",query(x,y,,n,));
                        if(y < x)
                                printf("%lld\n",query(y,x,,n,));
                }
                else if(s[] == 'C')
                        update(x,y,,n,);
        }
}


//COYG