遅延セグメント木

目的

長さnの数列valに対して、区間加算val[k]+=v(k=l,l+1,...r)と区間最大値の計算$\max_{l \le i\lt r}val[i]$の二つのクエリを$O(\log n)$で行うデータ構造。数列valの任意の要素は初期値0としている。

計算量

$O(N\log N)$

使い方

int n
数列valの長さ
long long[] val
数列val
long long query(int a,int b, long long add)
$\max_{a \le i\lt b}val[i]$をreturn。区間$[l,r)$にaddを可算。

ソースコード

struct segtree{
  
  int n;
  long long v[1000000];
  long long lazy[1000000];
  
  segtree(int n_){
    n=1;
    while(n<n_)n*=2;
    for(int i=0;i<2*n-1;++i){
      v[i]=0;
      lazy[i]=0;
    }
  }
 
  long long query(int a,int b,long long add){
    return query(0,n,a,b,0,add);
  }
 
  long long push(int k){
    v[k]+=lazy[k];
    if(2*k+2<2*n-1){
      lazy[2*k+1]+=lazy[k];
      lazy[2*k+2]+=lazy[k];
    }
    lazy[k]=0;
  }
  
  long long query(int l,int r,int a,int b,int k,long long add){
    push(k);
    if(r<=a||b<=l){
      return -(1LL<<60);
    }else if(a<=l&&r<=b){
      lazy[k]+=add;
      push(k);
      return v[k];
    }else{
      long long vl=query(l,(l+r)/2,a,b,2*k+1,add);
      long long vr=query((l+r)/2,r,a,b,2*k+2,add);
      v[k]=std::max(v[2*k+1],v[2*k+2]);
      return std::max(vl,vr);
    }
  }
  
};

検証

W-intervals/Educational DP Contest