题目训练网址（密码hpuacm）：https://vjudge.net/contest/248759

关于线段树原理什么的参考我转发来的两篇文章

递归版： https://blog.csdn.net/hpu2022/article/details/81946151

非递归版： https://blog.csdn.net/hpu2022/article/details/81946200

这里给出递归版的板子，其中包括区间更新，区间查询，单点更新，以及区间更新的lazy思想

什么是lazy思想，看下面

(3)线段树的区间修改：

线段树的区间修改也是将区间分成子区间，但是要加一个标记，称作懒惰标记。

标记的含义：

本节点的统计信息已经根据标记更新过了，但是本节点的子节点仍需要进行更新。

即，如果要给一个区间的所有值都加上1，那么，实际上并没有给这个区间的所有值都加上1，而是打个标记，记下来，这个节点所包含的区间需要加1.打上标记后，要根据标记更新本节点的统计信息，比如，如果本节点维护的是区间和，而本节点包含5个数，那么，打上+1的标记之后，要给本节点维护的和+5。这是向下延迟修改，但是向上显示的信息是修改以后的信息，所以查询的时候可以得到正确的结果。有的标记之间会相互影响，所以比较简单的做法是，每递归到一个区间，首先下推标记（若本节点有标记，就下推标记），然后再打上新的标记，这样仍然每个区间操作的复杂度是O(log2(n))。

 

标记有相对标记和绝对标记之分：

相对标记是将区间的所有数+a之类的操作，标记之间可以共存，跟打标记的顺序无关（跟顺序无关才是重点）。

所以，可以在区间修改的时候不下推标记，留到查询的时候再下推。

      注意：如果区间修改时不下推标记，那么PushUp函数中，必须考虑本节点的标记。

                 而如果所有操作都下推标记，那么PushUp函数可以不考虑本节点的标记，因为本节点的标记一定已经被下推了（也就是对本节点无效了）

绝对标记是将区间的所有数变成a之类的操作，打标记的顺序直接影响结果，

所以这种标记在区间修改的时候必须下推旧标记，不然会出错。

 

注意，有多个标记的时候，标记下推的顺序也很重要，错误的下推顺序可能会导致错误。

 

之所以要区分两种标记，是因为非递归线段树只能维护相对标记。

因为非递归线段树是自底向上直接修改分成的每个子区间，所以根本做不到在区间修改的时候下推标记。

非递归线段树一般不下推标记，而是自下而上求答案的过程中，根据标记更新答案。

板子：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
#define ls num << 1
#define rs num << 1 | 1

int sum[MAXN << 2], lazy[MAXN << 2];
int a[MAXN], n;
void push_up( int num )     // qiu he
{
    sum[num] = sum[ls] + sum[rs];
}
void build( int l, int r, int num )
{
    if( l == r )
    {
        sum[num] = a[l];
        return ;
    }
    int m = (l + r) >> 1;
    build(l, m, ls);
    build(m+1, r, rs);
    push_up(num);       // 递归以后上推
}
// a[L] += C 的操作
void update( int L, int C, int l, int r, int num )  // l, r表示当前节点区间，num表示当前节点编号
{
    if( l == r )    // 到叶节点，修改
    {
        sum[num] += C;
        return ;
    }
    int m = (l + r) >> 1;
    if( L <= m )    // 根据条件判断往左子树调用还是往右
        update(L, C, l, m, ls);
    else
        update(L, C, m+1, r, rs);
    push_up(num);       // 子节点更新了，所以本节点也需要更新信息
}
    // L, R表示操作区间，l, r表示当前节点区间，num表示当前节点编号
void update2( int L, int R, int C, int l, int r, int num )
{
    if( L <= l && r <= R )  // 如果本区间完全在操作区间[L,R]以内
    {
        sum[num] += C * (r - l + 1);    // 更新数字和，向上保持正确
        lazy[num] += C;  // 增加lazy标记，表示本区间的Sum正确，子区间的Sum仍需要根据lazy的值来调整
        return ;
    }
    int m = (l + r) >> 1;
    push_down(num, m - l + 1, r - m);
    if( L <= m )    // 这里判断左右子树跟[L,R]有无交集，有交集才递归
        update2(L, R, C, l, m, ls);
    if( R > m )
        update2(L, R, C, m+1, r, rs);
    push_up(num);
}
void push_down( int num, int ln, int rn )    // ln, rn为左子树，右子树的数字数量。
{
    if( lazy[num] )
    {
        lazy[ls] += lazy[num];    // 下推标记
        lazy[rs] += lazy[num];
        sum[ls] += lazy[num] * ln;   // 修改子节点的Sum使之与对应的lazy相对应
        sum[rs] += lazy[num] * rn;
        lazy[num] = 0;   // 清除本节点标记
    }
}
        // L, R表示操作区间，l, r表示当前节点区间，num表示当前节点编号
int query( int L, int R, int l, int r, int num )
{
    if( L <= l && r <= R )
        return sum[num];
           // 在区间内，直接返回
    int m = (l + r) >> 1;
    push_down(num, m - l + 1, r-m);

    int ans = 0;
    if( L <= m )
        ans += query(L, R, l, m, ls);
    if( R > m )
        ans += query(L, R, m, r, rs);
    return ans;
}

int main()
{






    return 0;
}

理解思想后，这个板子很好用

比如，稍做修改就AC一道题

HDU-1754

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 
这让很多学生很反感。 

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试，请处理到文件结束。 
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。 
学生ID编号分别从1编到N。 
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。 
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。 
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。 
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。 

Output

对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

Sample Output

5
6
5
9
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000+7;
#define ls num << 1
#define rs num << 1 | 1

int n, m;
int a[MAXN];
int sum[MAXN << 2];
void push_up( int num )
{
    sum[num] = max(sum[ls], sum[rs]);
}
void build( int l, int r, int num )
{
    if( l == r )
    {
        sum[num] = a[l];
        return ;
    }
    int m = (l + r) >> 1;
    build(l, m, ls);
    build(m+1, r, rs);
    push_up(num);
}
void update( int L, int C, int l, int r, int num )
{
    if( l == r )
    {
        sum[num] = C;
        return ;
    }
    int m = (l + r) >> 1;
    if( L <= m )
        update(L, C, l, m, ls);
    else
        update(L, C, m+1, r, rs);
    push_up(num);
}
int query( int L, int R, int l, int r, int num )
{
    if( L <= l && r <= R )
        return sum[num];
    int m = (l + r) >> 1;
    int ans1 = 0;
    int ans2 = 0;
    if( L <= m )
        ans1 = query(L, R, l, m, ls);
    if( R > m )
        ans2 = query(L, R, m+1, r, rs);
    return max(ans1, ans2);
}

int main()
{
    while( ~scanf("%d%d", &n, &m) )
    {
        for( int i=1; i<=n; i++ )
                scanf("%d", &a[i]);
        build(1, n, 1);
        for( int i=0; i<m; i++ )
        {
            char s[10];
            int a, b;
            scanf("%s", s);
            if( strcmp(s, "Q") == 0 )
            {
                scanf("%d%d", &a, &b);
                int res = query(a, b, 1, n, 1);
                printf("%d\n", res);
            }
            else //( strcmp(s, "U") == 0 )
            {
                scanf("%d%d", &a, &b);
                update(a, b, 1, n, 1);
            }

        }

    }

    return 0;
}