线段树：区间加与区间最大值

算法理解

节点保存它负责区间的最大值；整段被加同一个值时，不必立刻递归到底，只把增量记在 lazy 中。之后需要访问子节点时再下传，这就是懒标记。

• 复杂度：建树 O(n)，修改和查询均为 O(log n)。
• 注意：本模板求最大值；改为最小值或区间和时，无交集的返回值和父子合并方式也必须一起改。

模板代码

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
using pii=pair<int,int>;
const int mod=1e9+7;
//const int maxn=1e6+5;
#define lowbit(x) (x&(-x))
#define vc vector<int>
const int INI_MIN=-1e9;
const int INI_MAX=1e9;


struct node
{
    int data,lazy=0;
};

//建树
void build(const vector<int> &data, vector<node> &tree, int t,int left,int right)
{
    if (left==right)
    {
        tree[t].data=data[left];
        return;
    }
    int mid=(right+left)/2;
    build(data,tree,2*t,left,mid);  //左子树
    build(data,tree,2*t+1,mid+1,right); //右子树
    tree[t].data = max(tree[2*t].data,tree[2*t+1].data); //更新当前的最小值
}

//查找懒标记
void pushdown(vector<node> &tree,int t)
{
    if (tree[t].lazy!=0)
    {
        // 更新左子树
        tree[2*t].data+=tree[t].lazy;
        tree[2*t].lazy+=tree[t].lazy;
        //更新右子树
        tree[2*t+1].data+=tree[t].lazy;
        tree[2*t+1].lazy+=tree[t].lazy;
        //清空当前节点的懒标记
        tree[t].lazy=0;
    }
}

//区间查询
int query(vector<node> &tree,int t,int left,int right,int ql,int qr)
{
    if (ql>right || qr<left)
    {
        return INI_MIN;
    }
    if (ql<=left && qr>=right)
    {
        return tree[t].data;
    }

    int mid = (left+right)/2;

    pushdown(tree,t);

    int leftmax = query(tree,2*t,left,mid,ql,qr);
    int rightmax = query(tree,2*t+1,mid+1,right,ql,qr);

    return max(leftmax,rightmax);
}

//单点修改
void updata(vector<node> &tree, int t,int left, int right,int idx,int value)
{
    if (left==right)
    {
        tree[t].data = value;
        tree[t].lazy = 0; //找到目标点更新值
        return ;
    }

    int mid=(left+right)/2;
    pushdown(tree,t);

    if (idx<=mid)  //更新左子树
    {
        updata(tree,2*t,left,mid,idx,value);
    }
    else //更新右子树
    {
        updata(tree,2*t+1,mid+1,right,idx,value);
    }
    tree[t].data = max(tree[2*t].data,tree[2*t+1].data);
}

// 区间更新
void updatarange(vector<node> &tree, int t,int left,int right,int ql,int qr,int value)
{
    if (ql > right || qr < left)
    {
        return ; //区间无交集
    }
    if (ql <= left && qr >= right)
    {
        tree[t].data+=value;
        tree[t].lazy+=value;
        return ;
    }
    int mid=(left+right)/2;
    pushdown(tree,t);
    updatarange(tree,2*t,left,mid,ql,qr,value);
    updatarange(tree,2*t+1,mid+1,right,ql,qr,value);
    tree[t].data = max(tree[2*t].data,tree[2*t+1].data);
}


void solve()
{
    int n,m;
    cin>>n>>m;
    vector<int>data(n+1);
    vector<node>tree((n+1)*4);

    for(int i=1;i<=n;i++) 
        cin>>data[i];
    build(data,tree,1,1,n);
    while (m--)
    {
        int op;
        cin>>op;
        if (op==1)
        {
            int x,y,z;
            cin>>x>>y>>z;
            updatarange(tree,1,1,n,x,y,z);
        }
        else
        {
            int x,y;
            cin>>x>>y;
            cout<<query(tree,1,1,n,x,y)<<endl;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
//  cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

‍