线段树，每个节点都代表一个区间，左儿子和右儿子分别是父亲的左右子区间

线段树
线段树初始化
void build(int pos,int l,int r)
{
    if(l==r) {tree[pos]=a[l];return;}
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    tree[pos]=max(tree[rson],tree[lson]);
}




单点修改时，从根节点出发，二分地查询x所在区间，递归到左儿子或右儿子，直至叶子结点
O(log(n))
#define rson (2*(pos)+1)
#define lson (2*(pos))
void modify(int pos,int l,int r,int x,int y)//编号为pos,在区间l~r，找到x元素，将x改成y
{
    if(l==r) {tree[pos]=y;return;}
    int mid=(l+r)/2;
    if(x<=mid) modify(lson,l,mid,x,y)
    else modify(rson,mid+1,r,x,y);
    tree[pos]=max(tree[rson],tree[lson]);//pos区间最大值为左右子区间最大值
}




区间查询
int query(int pos,int l,int r,int x,int y)//查询x~y
{
    if(x<=l&&r<=y) return tree[pos];
    int mid=(l+r)>>1;
    int ret=0;//保存递归过程所获得的区间最值
    if(x<=mid) ret=max(ret,query(lson,l,mid,x,y));
    if(y>mid) ret=max(ret,query(rson,mid+1,r,x,y));
    return ret;
}




线段树维护
区间和同维护区间最大值想类似，把max改成+
区间修改
O(log(n))
void pushdown(int pos,int l,int r)
{
    int mid=(r+l)>>1;
    tsum[lson]+=lazy[pos]*(mid-l+1);
    lazy[lson]+=lazy[pos];
    tsum[rson]+=lazy[pos]*(r-mid);
    lazy[rson]+=lazy[pos];
    lazy[pos]=0;
}

void modify(int pos,int l,int r,int x,int y,int k)// x~y加上k
{
    if(x<=l&&r<=y){
        tsum[pos]=k*(r-l+1);//区间修改
        lazy[pos]+=k;
        return;
    }
    pushdown(pos,l,r);//l~r不完全包含于x~y
    int mid=(l+r)>>1;
    if(x<=mid) modify(lson,l,mid,x,y,k);
    if(y>mid) modify(rson,mid+1,r,x,y,k);
    tsum[pos]=tsum[rson]+tsum[lson];

}



修改过后的区间求和
int query(int pos,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return tsum[pos];
    pushdown(pos,l,r);
    int mid=(l+r)>>1;
    if(x<=mid) ret+=query(lson,l,mid,x,y);
    if(y>mid) ret+=query(rson,mid+1,r,x,y);
    return ret;
}




组合型区间操作
给定一定长度n的非负整数序列a,
A l r k 将a[l,r]每个值加上k
B l r k 将a[l,r] 每个值乘上k
p x y 询问 max(i=x~y)a[i]
Q x y 询问x~y区间和

 

/ Vijos / 题库 /

小白逛公园

 

描述

小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。

一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择**连续**的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。

那么，就请你来帮小白选择公园吧

 

 

通过读题，可得是关于区间问题，单点修改，以及区间子段求最大值

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define max2 500100
#define rson ((pos)*2+1)
#define lson ((pos)*2)
int a[max2];
struct node1{
    int sum,lmax,rmax,tmax;
};//sum代表节点所代表区间l-r的总和，lmax是从左边l开始向右的最大值，rmax是以右r结点向左的最值，tmax代表该段区间最值
node1 node[max2*4];
void sum(int pos,int l,int r){//初始化，求原始数据，每个节点的区间和，以及最值
    if(l==r) {node[pos].sum=a[l];
        node[pos].lmax=a[l];
        node[pos].rmax=a[l];
        node[pos].tmax=a[l];
        return;}
    int mid=(l+r)>>1;
    sum(lson,l,mid);
    sum(rson,mid+1,r);
    node[pos].sum=node[lson].sum+node[rson].sum;
    node[pos].lmax=max(node[lson].lmax,node[lson].sum+node[rson].lmax);//lmax等于子结点max(lmax,左儿子区间和+右儿子以左端点为起点的最大值)
    node[pos].rmax=max(node[rson].rmax,node[lson].rmax+node[rson].sum);
    node[pos].tmax=max(node[lson].rmax+node[rson].lmax,max(node[rson].tmax,node[lson].tmax));
}
void update(int pos,int l,int r,int x,int y)//单点修改，并用回溯法修改结点信息
{
    if(l==r) {node[pos].sum=y;
        node[pos].lmax=y;
        node[pos].rmax=y;
        node[pos].tmax=y;
        return;}
    int mid=(l+r)>>1;
    if(x<=mid) update(lson,l,mid,x,y);
    else update(rson,mid+1,r,x,y);
    node[pos].sum=node[lson].sum+node[rson].sum;
    node[pos].lmax=max(node[lson].lmax,node[lson].sum+node[rson].lmax);
    node[pos].rmax=max(node[rson].rmax,node[lson].rmax+node[rson].sum);
    node[pos].tmax=max(node[lson].rmax+node[rson].lmax,max(node[rson].tmax,node[lson].tmax));
}
node1 modify(int pos,int l,int r,int x,int y)//查询
{
    if(x<=l&&y>=r) {return node[pos];}
    int mid=(l+r)>>1;
    if(y<=mid) return modify(lson,l,mid,x,y);//区间在左
    if(x>mid) return modify(rson,mid+1,r,x,y);//区间x,y在右
    if(x<=mid&&y>mid){//区间x,y覆盖两边
        node1 tree,tree1,tree2;
        tree1=modify(lson,l,mid,x,y),tree2=modify(rson,mid+1,r,x,y);
        tree.lmax=max(tree1.lmax,tree1.sum+tree2.lmax);
        tree.rmax=max(tree2.rmax,tree2.sum+tree1.rmax);
        tree.sum=tree1.sum+tree2.sum;
        tree.tmax=max(tree1.rmax+tree2.lmax,max(tree1.tmax,tree2.tmax));
        return tree;
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sum(1,1,n);
    while(m--)
    {
        int k,p,s;
        cin>>k>>p>>s;
        ret1=0,ret2=0;
        if(k==1) {
            int x,y;
            x=min(p,s),y=max(p,s);
            cout<<modify(1,1,n,x,y).tmax<<endl;
        }
        else if(k==2){
            update(1,1,n,p,s);
        }
    }
}