遅延セグメントツリー - 競プロライブラリ

http://tsutaj.hatenablog.com/entry/2017/03/30/224339

AOJのDSLでverify
ToDo:抽象化した実装、動的構築
http://beet-aizu.hatenablog.com/entry/2017/12/01/225955
https://tomcatowl.github.io/post/ds-and-alg-1/
http://d.hatena.ne.jp/DEGwer/20131211/1386757368

区間更新区間最小

遅延セグ木で区間に対しての更新に対応

ソースコード

// 区間更新、区間最小の遅延セグメントツリー
struct RMQRUQ {
  int n;
  vector<int> dat, lazy;
 
  RMQRUQ(){}
  RMQRUQ(int n_) {
    n = 1; while(n < n_) n *= 2;
    dat.assign(n*2, INT_MAX);
    lazy.assign(n*2, INT_MAX);
  }
 
  void eval(int len, int k) {
    if(lazy[k] == INT_MAX) return;
    if(k*2+1 < n*2-1) {
      lazy[2*k+1] = lazy[k];
      lazy[2*k+2] = lazy[k];
    }
    dat[k] = lazy[k];
    lazy[k] = INT_MAX;
  }
 
  // [a, b)
  ll update(int a, int b, ll x, int k, int l, int r) {
    eval(r-l, k);
    if(b <= l || r <= a) return dat[k];
    if(a <= l && r <= b) {
      lazy[k] = x;
      return lazy[k];
    }
    return dat[k] = min(update(a, b, x, 2*k+1, l, (l+r)/2), update(a, b, x, 2*k+2, (l+r)/2, r));
  }
  ll update(int a, int b, ll x) { return update(a, b, x, 0, 0, n); }
 
  // [a, b)
  ll query(int a, int b, int k, int l, int r) {
    eval(r-l, k);
    if(b <= l || r <= a) return INT_MAX;
    if(a <= l && r <= b) return dat[k];
    ll vl = query(a, b, 2*k+1, l, (l+r)/2);
    ll vr = query(a, b, 2*k+2, (l+r)/2, r);
    return min(vl, vr);
  }
  ll query(int a, int b) { return query(a, b, 0, 0, n); }
};
 

区間加算区間和

ソースコード

// 区間加算区間和
struct RSQRAQ {
  int n;
  vector<ll> dat, lazy;
 
  RSQRAQ(){}
  RSQRAQ(int n_) {
    n = 1; while(n < n_) n *= 2;
    dat.assign(n*2, 0);
    lazy.assign(n*2, 0);
  }
 
  void eval(int len, int k) {
    if(lazy[k] == 0) return;
    if(k*2+1 < n*2-1) {
      lazy[2*k+1] += lazy[k];
      lazy[2*k+2] += lazy[k];
    }
    dat[k] += lazy[k]*len;
    lazy[k] = 0;
  }
 
  // [a, b)
  ll update(int a, int b, ll x, int k, int l, int r) {
    eval(r-l, k);
    if(b <= l || r <= a) return dat[k];
    if(a <= l && r <= b) {
      lazy[k] += x;
      return dat[k] + lazy[k]*(r-l);
    }
    return dat[k] = update(a, b, x, 2*k+1, l, (l+r)/2) + update(a, b, x, 2*k+2, (l+r)/2, r);
  }
  ll update(int a, int b, ll x) { return update(a, b, x, 0, 0, n); }
 
  // [a, b)
  ll query(int a, int b, int k, int l, int r) {
    eval(r-l, k);
    if(b <= l || r <= a) return 0;
    if(a <= l && r <= b) return dat[k];
    ll vl = query(a, b, 2*k+1, l, (l+r)/2);
    ll vr = query(a, b, 2*k+2, (l+r)/2, r);
    return vl + vr;
  }
  ll query(int a, int b) { return query(a, b, 0, 0, n); }
}; 

starrysky木

ソースコード

// 区間加算、区間最大のstarrysky木
struct starrysky {
  int n;
  const int init_ = 0;
  VI lazym, lazya;
  starrysky(){}
  starrysky(int n_) {init(n_);}
  void init(int n_) {
    n = 1; while(n<n_) n *= 2;
    lazym.assign(2*n-1, init_);
    lazya.assign(2*n-1, 0);
  }
  // [a, b)
  void add(int a, int b, int x) {add(a, b, x, 0, 0, n);}
  void add(int a, int b, int x, int k, int l, int r) {
    if(r <= a || b <= l) return;
    if(a <= l && r <= b) lazya[k] += x;
    else {
      add(a, b, x, k*2+1, l, (l+r)/2);
      add(a, b, x, k*2+2, (l+r)/2, r);
      lazym[k] = max(lazym[k*2+1]+lazya[k*2+1],
                      lazym[k*2+2]+lazya[k+2+2]);
    }
  }
  // [a, b)
  int query(int a, int b) {return query(a, b, 0, 0, n);}
  int query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return init_;
    if(a <= l && r <= b) return lazym[k] + lazya[k];
    int vl = query(a, b, k*2+1, l, (l+r)/2),
        vr = query(a, b, k*2+2, (l+r)/2, r);
    return max(vl, vr)+lazya[k];
  }
};