线段树

线段树模板1（基础）

P3372 【模板】线段树 1

（上：编号，下：区间管辖范围）

             [1]
            [0~5]
             /\
            /  \
           /    \
          /      \
         /        \
       [2]        [3]
      [0~3]      [4~5]
       /\          /\
      /  \        /  \      
     /    \      /    \
   [4]    [5]  [6]    [7]
  [0~1]  [2~3] [4]    [5]
   /\      /\    \      \
 [8][9] [10][11] [12]   [13]
[0]  [1][2]  [3]  [4]    [5]
   

不断二分查找支持懒标记的树状结构。

左儿子

位运算提速。

int l_l(int k){//左儿子 
  return k<<1;
}

右儿子

int r_r(int k){//右儿子 
  return k<<1|1;
}

树的存储

将序列存储成树状结构。

void b_t(int l,int r,int k){//建树 
  if(l==r){//若到达叶节点 
    t_r[k]=a_a[l];//存储a数组的值
    return;
  }
  int m_i=(l+r)>>1;
  b_t(l,m_i,l_l(k));//建子树 
  b_t(m_i+1,r,r_r(k));
  u_p(k); //更新信息 
}

懒标记

快捷存储状态，在访问时，在将要访问的点同时更新（懒标记下传）。这样原本要更新 $10$ 次，但是现在，在访问前只需更新 $1$ 次即可（要更新的数是原来要更新累计的）。

在扫区间时，只要区间在要更新范围内，在区间上打懒标记。这样在询问前将区间懒标记释放即可。

void a_d(int l,int r,int x,int y,int k,int v){//区间加 
  if(x<=l&&r<=y){//在要求范围内 
    t_r[k]+=(r-l+1)*v;//更新区间
    l_n[k]+=v;//懒标记 
    return ;
  }
  p_d(k,l,r);//更新懒标记 
  int m_i=(l+r)>>1;
  if(m_i>=x)a_d(l,m_i,x,y,l_l(k),v);//遍历左右子树 
  if(m_i<y)a_d(m_i+1,r,x,y,r_r(k),v);
  u_p(k);//更新节点 
}

更新节点

void u_p(int k){//更新当前节点 
  t_r[k]=t_r[l_l(k)]+t_r[r_r(k)];
}

在子节点遍历完时，回溯到区间时。要更新区间，区间存的是区间和，区间内节点值被更新，区间值也要更新。

区间修改（加值）

遍历区间在要更新的区间内，将此区间打上懒标记并更新，继续分左右子树遍历即可。

void a_d(int l,int r,int x,int y,int k,int v){//区间加 
  if(x<=l&&r<=y){//在要求范围内 
    t_r[k]+=(r-l+1)*v;
    l_n[k]+=v;//懒标记 
    return ;
  }
  p_d(k,l,r);//更新懒标记 
  int m_i=(l+r)>>1;
  if(m_i>=x)a_d(l,m_i,x,y,l_l(k),v);//遍历左右子树 
  if(m_i<y)a_d(m_i+1,r,x,y,r_r(k),v);
  u_p(k);//更新节点 
}

懒标记释放

当前节点只用更新区间的左右子树的值和懒标记，遍历完这个点后，直接遍历左右子树就可以保证懒标记传递完整。回溯时，也要及时更新区间维护的值。

void p_d(int k,int l,int r){//更新懒标记 
  int m_i=(l+r)>>1;
  l_n[l_l(k)]+=l_n[k];//懒标记下传 
  l_n[r_r(k)]+=l_n[k];
  t_r[l_l(k)]+=l_n[k]*(m_i-l+1);//更新子树 
  t_r[r_r(k)]+=l_n[k]*(r-m_i);
  l_n[k]=0;//清空懒标记 
}

查询

与区间修改相似，注意在查询前先释放懒标记。

long long s_m(int l,int r,int x,int y,int k){//求区间和 
  long long a_s=0;
  if(x<=l&&r<=y)return t_r[k];//在区间范围内，返回区间和 
  p_d(k,l,r);
  int m_i=(l+r)>>1;
  if(m_i>=x)a_s+=s_m(l,m_i,x,y,l_l(k));//找左右子树 
  if(m_i<y)a_s+=s_m(m_i+1,r,x,y,r_r(k));
  return a_s;
} 

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){
  long long x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const int o_o=3e5+10;//数组空间 
long long n,m;
long long a_a[o_o];//原序列 
long long t_r[o_o];//线段树 
long long l_n[o_o];//懒标记 
int l_l(int k){//左儿子 
  return k<<1;
}
int r_r(int k){//右儿子 
  return k<<1|1;
}
void u_p(int k){//更新当前节点 
  t_r[k]=t_r[l_l(k)]+t_r[r_r(k)];
}
void b_t(int l,int r,int k){//建树 
  if(l==r){//叶节点，赋值 
    t_r[k]=a_a[l];
    return;
  }
  int m_i=(l+r)>>1;
  b_t(l,m_i,l_l(k));//建子树 
  b_t(m_i+1,r,r_r(k));
  u_p(k);
}
void p_d(int k,int l,int r){//更新懒标记 
  int m_i=(l+r)>>1;
  l_n[l_l(k)]+=l_n[k];//懒标记下传 
  l_n[r_r(k)]+=l_n[k];
  t_r[l_l(k)]+=l_n[k]*(m_i-l+1);//更新子树 
  t_r[r_r(k)]+=l_n[k]*(r-m_i);
  l_n[k]=0;//清空懒标记 
}
void a_d(int l,int r,int x,int y,int k,int v){//区间加 
  if(x<=l&&r<=y){//在要求范围内 
    t_r[k]+=(r-l+1)*v;
    l_n[k]+=v;//懒标记 
    return ;
  }
  p_d(k,l,r);//更新懒标记 
  int m_i=(l+r)>>1;
  if(m_i>=x)a_d(l,m_i,x,y,l_l(k),v);//遍历左右子树 
  if(m_i<y)a_d(m_i+1,r,x,y,r_r(k),v);
  u_p(k);//更新节点 
}
long long s_m(int l,int r,int x,int y,int k){//求区间和 
  long long a_s=0;
  if(x<=l&&r<=y)return t_r[k];//在区间范围内，返回区间和 
  p_d(k,l,r);
  int m_i=(l+r)>>1;
  if(m_i>=x)a_s+=s_m(l,m_i,x,y,l_l(k));//找左右子树 
  if(m_i<y)a_s+=s_m(m_i+1,r,x,y,r_r(k));
  return a_s;
}
int main(){
    n=r_r(),m=r_r();
    for(int i=1;i<=n;i++)a_a[i]=r_r();//读入原序列 
    b_t(1,n,1);//建树 
    while(m--){
      int op=r_r();
      if(op==1){//区间加 
        int l=r_r(),r=r_r(),v=r_r();
        a_d(1,n,l,r,1,v);
    }else {//区间求和 
      int l=r_r(),r=r_r();
      printf("%lld\n",s_m(1,n,l,r,1));
    }
  }
    return 0;
}

线段树模板2（深度认知）

P3373 【模板】线段树 2

比上一道题多一个区间乘操作，注意符号运算有优先级。

$(a+b)\times c=a\times c+b\times c$。

$($ 加法懒标记 $+$ 值 $)\times $ 乘法懒标记 $=$ 加法懒标记 $\times$ 乘法懒标记 $+$ 值 $\times$ 乘法懒标记

即时取模

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){
  long long x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const int o_o=3e5+10;//数组空间 
int a_a[o_o],p;
struct po{
  long long v;//节点值 
  long long c_h;//乘法懒标记 
  long long a_d;//加法懒标记 
}t_r[o_o];
int l_l(int k){//左儿子 
  return k<<1;
}
int r_r(int k){//右儿子 
  return k<<1|1;
}
void u_p(int k){//更新当前节点的值 
  t_r[k].v=(t_r[l_l(k)].v+t_r[r_r(k)].v)%p;
}
void b_t(int l,int r,int k){//建树 
  t_r[k].c_h=1;//初始化，乘法懒标记（要设为 1，否则所有乘运算都是无用功） 
  t_r[k].a_d=0;//初始化，加法懒标记 
  if(l==r){//是节点，记录 
    t_r[k].v=a_a[l];
    return ;
  }
  int m_i=(l+r)>>1;
  b_t(l,m_i,l_l(k));//左子树 
  b_t(m_i+1,r,r_r(k));//右子树 
  u_p(k);//更新节点变量 
}
void p_d(int k,int l,int r){//懒标记下穿（运算优先级，先乘再加）  
  int m_i=(l+r)>>1;
  
  //更新儿子数值 
  t_r[l_l(k)].v=(t_r[l_l(k)].v*t_r[k].c_h)%p;//处理左儿子的值的乘法值增加 
  t_r[l_l(k)].v=(t_r[l_l(k)].v+t_r[k].a_d*(m_i-l+1))%p;//处理左儿子的值的加法值增加
  t_r[r_r(k)].v=(t_r[r_r(k)].v*t_r[k].c_h)%p;//处理右儿子的值的乘法值增加 
  t_r[r_r(k)].v=(t_r[r_r(k)].v+t_r[k].a_d*(r-m_i))%p;//处理右儿子的值的加法值增加
  
  //更新儿子乘法懒标记 
  t_r[l_l(k)].c_h=(t_r[l_l(k)].c_h*t_r[k].c_h)%p;//更新左儿子乘法懒标记（标记下传） 
  t_r[r_r(k)].c_h=(t_r[r_r(k)].c_h*t_r[k].c_h)%p;//更新右儿子乘法懒标记（标记下传） 
  
  //更新儿子加法懒标记 
  t_r[l_l(k)].a_d=(t_r[l_l(k)].a_d*t_r[k].c_h)%p;//更新左儿子加法懒标记经过乘法后的变化（标记下传） 
  t_r[l_l(k)].a_d=(t_r[l_l(k)].a_d+t_r[k].a_d)%p;//更新左儿子加法懒标记（标记下传） 
  t_r[r_r(k)].a_d=(t_r[r_r(k)].a_d*t_r[k].c_h)%p;//更新右儿子加法懒标记经过乘法后的变化（标记下传） 
  t_r[r_r(k)].a_d=(t_r[r_r(k)].a_d+t_r[k].a_d)%p;//更新左儿子加法懒标记（标记下传） 
  
  //清空懒标记 
  t_r[k].c_h=1;
  t_r[k].a_d=0;
}
void c_h(int l,int r,int x,int y,int k,long long v){//区间修改——乘法 
  if(x<=l&&r<=y){
    t_r[k].v=(t_r[k].v*v)%p;//更新区间值 
    t_r[k].c_h=(t_r[k].c_h*v)%p;//更新乘法懒标记 
    t_r[k].a_d=(t_r[k].a_d*v)%p;//乘法的优先运算比加法高，所以加法要加括号，把括号拆开，加法运算也要更新 
    return ;
  }
  p_d(k,l,r);//懒标记下传 
  int m_i=(l+r)>>1;
  if(m_i>=x)c_h(l,m_i,x,y,l_l(k),v);//左子树 
  if(m_i<y)c_h(m_i+1,r,x,y,r_r(k),v);//右子树 
  u_p(k);//回溯更新节点 
}
void a_d(int l,int r,int x,int y,int k,long long v){//区间修改——加法 
  if(x<=l&&r<=y){
    t_r[k].a_d=(t_r[k].a_d+v)%p;//更新加法懒标记 
    t_r[k].v=(t_r[k].v+v*(r-l+1))%p;//更新值 
    return ;
  }
  p_d(k,l,r);//懒标记下传 
  int m_i=(l+r)>>1;
  if(m_i>=x)a_d(l,m_i,x,y,l_l(k),v);//左子树 
  if(m_i<y)a_d(m_i+1,r,x,y,r_r(k),v);//右子树 
  u_p(k);//回溯更新节点 
}
long long s_m(int l,int r,int x,int y,int k){//区间查询 
  long long a_s=0;//统计结果 
  if(x<=l&&r<=y)return t_r[k].v;//在区间范围内，直接调用区间值 
  p_d(k,l,r);
  int m_i=(l+r)>>1;
  if(m_i>=x)a_s=(a_s+s_m(l,m_i,x,y,l_l(k)))%p;//向左查 
  if(m_i<y)a_s=(a_s+s_m(m_i+1,r,x,y,r_r(k)))%p;//向右查 
  return a_s%p;
}
int main(){
  int n=r_r(),m=r_r();
  p=r_r();
  for(int i=1;i<=n;i++)a_a[i]=r_r();//读取原序列 
  b_t(1,n,1);//建树 
  while(m--){
    int op=r_r();
    if(op==1){
      int l=r_r(),r=r_r(),v=r_r();
      c_h(1,n,l,r,1,v);//区间修改——乘法 
    }else if(op==2){
      int l=r_r(),r=r_r(),v=r_r();
      a_d(1,n,l,r,1,v);//区间修改——加法 
    }else {
      int l=r_r(),r=r_r();
      printf("%lld\n",s_m(1,n,l,r,1));//区间求和 
    }
  }
  return 0;
}

线段树模板3（深刻理解）

P6242 【模板】线段树 3

比前面的模板有特色地地方在于维护最大值，历史最大值，区间更新最小值。

主要难点在与最小值的维护。维护最小值我们需要四个信息：区间最大值，最大值个数，区间历史最大值，区间严格次大值。

这样在更新区间最小值时，会出现以下三种情况。

• 更新值 $>$ 区间最大值。（那么此时直接跳出，因为没有只需要更新）

• 更新值 $<$ 区间最大值，但是 $>$ 区间次大值，那么将现在的区间和减去最大值个数 $\times ($ 最大值 $-$ 区间要更新的最小值 $)$，即完成了维护，再更新区间最大值，更新为区间要更新的最小值。

• 更新值 $<$ 区间次大值，那么继续向下搜。

区间历史最大值虽然不用参与讨论，但是要时刻维护（操作 $5$）

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>

using namespace std;

long long r_r(){//快读 
  
  long long k=0,f=1;
  char c=getchar();
  
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar();
  }
  
  return k*f;
}

const int o_o=3e6+10;//数组大小 
const int m_a=2e9+10;//最大值 

struct po{//树的节点（覆盖区间） 
  
  int l,r;//区间覆盖范围 
  
  long long m_x;//区间最大值 
  long long x_p;//最大值个数 
  long long m_x_;//区间历史最大值 
  long long m_i_x;//区间严格次大值 
  
  long long s_m;//区间和 
  
  long long a_d_1;//最大值区间加减标记 
  long long a_d_1_;//最大值历史区间最大加减标记 
  long long a_d_2;//非最大值区间加减标记 
  long long a_d_2_;//非最大值区间最大加减标记 
  
}t_r[o_o<<2];//线段树区间节点 

long long a_a[o_o];//原序列 

int l_l(int k){//左子树 
  return k<<1;
}

int r_r(int k){//右子树 
  return k<<1|1;
}

void u_p(int k){//更新节点信息 
  
  t_r[k].s_m=t_r[l_l(k)].s_m+t_r[r_r(k)].s_m;//更新区间和 
  
  //更新区间历史最大值 
  t_r[k].m_x_=max(t_r[l_l(k)].m_x_,t_r[r_r(k)].m_x_);
  
  if(t_r[l_l(k)].m_x==t_r[r_r(k)].m_x){//左右儿子最大值相同 
  
    //更新节点最大值
    t_r[k].m_x=t_r[l_l(k)].m_x; 
    
    //更新节点次大值 
    t_r[k].m_i_x=max(t_r[l_l(k)].m_i_x,t_r[r_r(k)].m_i_x);
    
    //更新最大值数量 
    t_r[k].x_p=t_r[l_l(k)].x_p+t_r[r_r(k)].x_p;
    
  }else if(t_r[l_l(k)].m_x>t_r[r_r(k)].m_x){//左儿子最大值更大 
  
    //更新节点最大值 
    t_r[k].m_x=t_r[l_l(k)].m_x;
    
    //更新节点次大值  
    t_r[k].m_i_x=max(t_r[l_l(k)].m_i_x,t_r[r_r(k)].m_x);
    
    //更新最大值数量
    t_r[k].x_p=t_r[l_l(k)].x_p; 
    
  }else{//右儿子最大值更大 
  
    //更新节点最大值 
    t_r[k].m_x=t_r[r_r(k)].m_x;
    
    //更新节点次大值 
    t_r[k].m_i_x=max(t_r[l_l(k)].m_x,t_r[r_r(k)].m_i_x);
    
    //更新节点最大值 
    t_r[k].x_p=t_r[r_r(k)].x_p;
  }
}

//更新区间和标记 
//k 当前节点坐标，k_1 最大值区间加减标记，k_1_ 最大值历史区间最大加减标记 
//k_2 非最大值区间加减标记，k_2_ 非最大值区间最大加减标记 
void u_d(int k,long long k_1,long long k_1_,long long k_2,long long k_2_){
  
  //更新区间和 
  t_r[k].s_m+=k_1*t_r[k].x_p+k_2*(t_r[k].r-t_r[k].l+1-t_r[k].x_p);
  
  //更新区间历史最大值 
  t_r[k].m_x_=max(t_r[k].m_x_,t_r[k].m_x+k_1_);
  
  //更新区间历史最大加减标记 
  t_r[k].a_d_1_=max(t_r[k].a_d_1_,t_r[k].a_d_1+k_1_);
  
  //更新区间最大值 
  t_r[k].m_x+=k_1;
  
  //更新区间最大加减标记 
  t_r[k].a_d_1+=k_1;
  
  //更新非最大值区间加减标记
  t_r[k].a_d_2_=max(t_r[k].a_d_2_,t_r[k].a_d_2+k_2_);
  
  //当前节点有次大值，更新次大值 
  if(t_r[k].m_i_x!=-m_a)t_r[k].m_i_x+=k_2;
  
  //更新非最大值区间最大加减标记
  t_r[k].a_d_2+=k_2;
  
}

void p_d(int k){//下传懒标记 
  
  //记录儿子中的最大值 
  int m_s=max(t_r[l_l(k)].m_x,t_r[r_r(k)].m_x);
  
  //左儿子最大值大，以最大值身份更新区间 
  if(t_r[l_l(k)].m_x==m_s)
    u_d(l_l(k),t_r[k].a_d_1,t_r[k].a_d_1_,t_r[k].a_d_2,t_r[k].a_d_2_);
  
  //左儿子最大值小，以次大值身份更新区间 
  else u_d(l_l(k),t_r[k].a_d_2,t_r[k].a_d_2_,t_r[k].a_d_2,t_r[k].a_d_2_);
  
  //右儿子最大值大，以最大值身份更新区间 
  if(t_r[r_r(k)].m_x==m_s)
    u_d(r_r(k),t_r[k].a_d_1,t_r[k].a_d_1_,t_r[k].a_d_2,t_r[k].a_d_2_);
  
  //右儿子最大值小，以次大值身份更新区间 
  else u_d(r_r(k),t_r[k].a_d_2,t_r[k].a_d_2_,t_r[k].a_d_2,t_r[k].a_d_2_);
  
  //清除标记 
  t_r[k].a_d_1=t_r[k].a_d_1_=0;
  t_r[k].a_d_2=t_r[k].a_d_2_=0;
  
}

void b_t(int k,int l,int r){//建树 
  
  t_r[k].l=l;
  t_r[k].r=r;//初始化左右区间 
  t_r[k].a_d_1=t_r[k].a_d_1_=0;
  t_r[k].a_d_2=t_r[k].a_d_2_=0;//初始化区间加减标记 
  
  if(l==r){//是节点存储信息 
  
    t_r[k].s_m=a_a[l];//存储节点初始信息
    t_r[k].m_x_=t_r[k].m_x=a_a[l];//最大值和历史最大值初始化 
    t_r[k].m_i_x=-m_a;//初始化区间严格次大值 
    t_r[k].x_p=1;//初始化区间最大值个数 
    
    return;
  }
  
  int m_d=(l+r)>>1;
  
  b_t(l_l(k),l,m_d);//左子树 
  b_t(r_r(k),m_d+1,r);//右子树 
  
  u_p(k);//更新节点信息 
  
}

void a_d(int k,int l,int r,int v){//区间加减修改 
  
  if(t_r[k].l>r||t_r[k].r<l)return;//区间不在询问范围内 
  
  if(l<=t_r[k].l&&t_r[k].r<=r){//区间被询问范围包含 
  
    u_d(k,v,v,v,v);//更新节点值 
    
    return;
  }
  
  p_d(k);//下传懒标记 
  
  a_d(l_l(k),l,r,v);//左子树 
  a_d(r_r(k),l,r,v);//右子树 
  
  u_p(k);//更新节点信息 
  
}

void m_i(int k,int l,int r,int v){//区间最小值修改 
  
  if(t_r[k].l>r||t_r[k].r<l||v>=t_r[k].m_x)return;//区间不在询问范围内
  
  if(l<=t_r[k].l&&t_r[k].r<=r&&v>t_r[k].m_i_x){//区间被询问范围包含
   
    //更新最大区间加减标记和历史最大标记，保证更新后不会超过更新最小值
    //若区间规定最小值比原值小，区间修改值变为负数，多了多少，就减多少 
    u_d(k,v-t_r[k].m_x,v-t_r[k].m_x,0,0);
    
    return;
  }
  
  p_d(k);//下传懒标记 
  
  m_i(l_l(k),l,r,v);//左子树 
  m_i(r_r(k),l,r,v);//右子树 
  
  u_p(k);//更新节点信息 
}

long long s_m(int k,int l,int r){//求区间和 
  
  long long a_s; 
  
  if(t_r[k].l>r||t_r[k].r<l)return 0;//不在范围内，不更新答案 
  
  //被范围包含，直接返回提前处理好的区间和 
  if(l<=t_r[k].l&&t_r[k].r<=r)return t_r[k].s_m;
  
  p_d(k);//标记下传 
  
  a_s=s_m(l_l(k),l,r)+s_m(r_r(k),l,r);//统计答案 
  
  return a_s;//返回统计结果 
}

long long a_x(int k,int l,int r){//求区间最大值 
  
  long long a_s;
  
  if(t_r[k].l>r||t_r[k].r<l)return -m_a;//不在范围内，返回不更新答案的值 
  
  //被范围包含，直接返回提前处理好的区间和 
  if(l<=t_r[k].l&&t_r[k].r<=r)return t_r[k].m_x;
  
  p_d(k);//标记下传 
  
  a_s=max(a_x(l_l(k),l,r),a_x(r_r(k),l,r));//找最大值 
  
  return a_s;//返回统计结果 
  
}

long long b_x(int k,int l,int r){//求区间历史最大值 
  
  long long a_s; 
  
  if(t_r[k].l>r||t_r[k].r<l)return -m_a;//不在范围内，返回不更新答案的值 
  
  //被范围包含，直接返回提前处理好的区间和 
  if(l<=t_r[k].l&&t_r[k].r<=r)return t_r[k].m_x_;
  
  p_d(k);//标记下传 
  
  a_s=max(b_x(r_r(k),l,r),b_x(l_l(k),l,r));//找最大值 
  
  return a_s;//返回统计结果 
  
}

int main(){
  
  int n=r_r(),m=r_r();
  
  for(int i=1;i<=n;i++)a_a[i]=r_r();//读入序列 
  
  b_t(1,1,n);//建图 
  
  while(m--){
    
    int op=r_r();
    
    if(op==1){
      
      int l=r_r(),r=r_r(),v=r_r();
      
      a_d(1,l,r,v);//区间加 
      
    }else if(op==2){
      
      int l=r_r(),r=r_r(),v=r_r();
      
      m_i(1,l,r,v);//区间最小值 
      
    }else if(op==3){
      
      int l=r_r(),r=r_r();
      
      printf("%lld\n",s_m(1,l,r));//区间和 
      
    }else if(op==4){
      
      int l=r_r(),r=r_r();
      
      printf("%lld\n",a_x(1,l,r));//区间最大值 
      
    }else {
      
      int l=r_r(),r=r_r();
      
      printf("%lld\n",b_x(1,l,r));//区间历史最大值 
      
    }
    
  }
  
  return 0;
}