线段树

线段树的基本用途

1. 查询某个区间

2. 修改某个区间或点

是不是和树状数组很像?

注意

线段树的数组一定要开\(4n\)

建树代码 （sum）

通过二叉树的性质可知：对于一个父节点，它的左右两个儿子节点分别为i乘以2，i乘以2+1，

由此可以用数组模拟线段树：

inline void build(int p,int l,int r){
 lazy[p]=0;
 if(l==r){dat[p]=a[l];return;}
 int mid=(l+r)>>1;
 build(ls,l,mid);
 build(rs,mid+1,r);
 dat[p]=dat[ls]+dat[rs];
}

\(lazy\)标记

学一个东西，首先要知道这个东西有什么用，\(SO\)：

区间修改的指令，\([l,r]\)可能要逐一修改，时间复杂度增加到\(O(N)\) ,这时延迟标记j派上用场了，如果之后的查询指令中，没有用到\([l,r]\)的子区间，那么更新就是无用的。

这个标记的意思是“该节点曾经被修改过，可它的子节点未被更新”

之前更新的时候是\(pushup\)——递归从下往上，这个很好理解，因为信息一开始都在最底层叶子节点，

所以\(pushdown\)时，区间查询，所以如果要向下更新，就要调整循序，不然向下递归时\(pushdown\)就不太行了

所以每次更新，只要更新它的子节点即可

代码如下，注意函数的先后顺序

inline void down(int p,int l,int r){
  int mid=l+r>>1;
  lazy[ls]+=lazy[p];//把标记下传给左右儿子
  dat[ls]+=lazy[p]*(mid-l+1);
  lazy[rs]+=lazy[p];
  dat[rs]+=lazy[p]*(r-mid);
  lazy[p]=0;//标记清零
  return;
}

inline void update(int p,int x,int y,int l,int r,int k){//p表示当前节点,x,y表示修改区间,l,r表示当前区间
  if(x<=l&&y>=r){//如果这个区间被完全覆盖
    dat[p]+=k*(r-l+1);
    lazy[p]+=k;
    return;
  }
  down(p,l,r);//更新了就一定要下传标记
  int mid=l+r>>1;
  if(x<=mid) update(ls,x,y,l,mid,k);//如果两个子区间被完全覆盖
  if(y>mid) update(rs,x,y,mid+1,r,k);
  dat[p]=dat[ls]+dat[rs];//更新
}

完整代码

#include 
#include 
#include 
#define ls p<<1//用位运算会更快
#define int long long
#define rs p<<1|1
using namespace std;
int n,m,a[4000005],dat[4000005],lazy[4000005];
int q;
inline int read(){
  int x=0;int f=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
  return x*f;
}
inline void down(int p,int l,int r){
  int mid=l+r>>1;
  lazy[ls]+=lazy[p];
  dat[ls]+=lazy[p]*(mid-l+1);
  lazy[rs]+=lazy[p];
  dat[rs]+=lazy[p]*(r-mid);
  lazy[p]=0;
  return;
}
inline void build(int p,int l,int r){
  lazy[p]=0;
  if(l==r){dat[p]=a[l];return;}
  int mid=(l+r)>>1;
  build(ls,l,mid);
  build(rs,mid+1,r);
  dat[p]=dat[ls]+dat[rs];
}
inline void update(int p,int x,int y,int l,int r,int k){
  if(x<=l&&y>=r){
    dat[p]+=k*(r-l+1);
    lazy[p]+=k;
    return;
  }
  down(p,l,r);
  int mid=l+r>>1;
  if(x<=mid) update(ls,x,y,l,mid,k);
  if(y>mid) update(rs,x,y,mid+1,r,k);
  dat[p]=dat[ls]+dat[rs];
}
inline int query(int p,int x,int y,int l,int r){
  int res=0;
  if(x<=l&&y>=r) return dat[p];
  int mid=l+r>>1;
  down(p,l,r);
  if(x<=mid) res+=query(ls,x,y,l,mid);
  if(y>mid) res+=query(rs,x,y,mid+1,r);
  return res;
}
signed main(){
  n=read();q=read();
  for(int i=1;i<=n;i++)
    a[i]=read();
  build(1,1,n);
  for(int j=1;j<=q;j++){
    int c,x,y,k,i1;
    c=read();
    if(c==1){
      x=read();y=read();k=read();
      update(1,x,y,1,n,k);
    }
    else {
      x=read();y=read();
      cout<