区間に等差数列を作用させる遅延セグメントツリー

たまに見る割にまとまった記事がない気がしたので

区間に等差数列を作用させる遅延セグメントツリーとは

長さ $N$ の数列 $A_0, \dots, A_{N-1}$ に対し次のような操作が全て $O(\log N)$ で行えます。

$A_l, A_{l+1}, \dots, A_{r-1}$ をそれぞれ $b,\ a+b,\ 2a+b,\ \dots, \ (r-l)a+b$ で更新する。

$A_l, A_{l+1}, \dots, A_{r-1}$ の最小値/最大値/総和を取得する。

後程述べますが、少し変えると区間等差数列加算・区間和も扱えます。

仕組み

次のような更新を目標にします。

$A_l, A_{l+1}, \dots, A_{r-1}$ をそれぞれ $la+b,\ (l+1)a+b,\ \dots, \ (r-1)a+b$ で更新する。

これはセグ木のノードに最小値、最大値、総和、左端/右端のindexを持たせることで実現できます。

ノードのマージはそれぞれのminやmaxをそのまま取ればよいです。

作用素の作用については、区間 $[l,r)$ を $i \times a+b$ で更新するとき、

$a \geq 0$ なら左端が新しい最小値となり、右端が新しい最大値となる

$a < 0$ なら左端が新しい最大値となり、右端が新しい最小値となる

ことに注意することで最小値/最大値を計算できます。

総和は等差数列の和なので更新後の総和を計算して上書きすればよいです。

ノードのマージと作用素の作用が入れ替え可能なので（略）、無事遅延セグ木に乗せることができました。

添え字がずれていますが、 $i \times a+b$ の代わりに $i \times a+(b-la)$ で更新することで冒頭で述べた変更と一致します。

コード

ACLのlazy_segtreeを継承しています。初項の変更を自動的に行います。

using ll = long long;

// 区間min & 区間max & 区間sum & 区間等差更新
namespace arithmetic {

const ll LINF = ll(4e18);
const int INF = int(1e9) + 10;

struct S {
  ll min, max, sum;
  int l, r;
};
struct F {
  ll a, b;
};
S op(S s, S t) {
  return {min(s.min, t.min), max(s.max, t.max), s.sum + t.sum, min(s.l, t.l),
          max(s.r, t.r)};
}
S e() { return {LINF, -LINF, 0, INF, -INF}; }
S mapping(F f, S s) {
  if (f.a == LINF) return s;
  if (f.a >= 0)
    return {f.a * s.l + f.b, f.a * (s.r - 1) + f.b,
            (f.a * (s.l + s.r - 1) + f.b * 2) * (s.r - s.l) / 2, s.l, s.r};
  else
    return {f.a * (s.r - 1) + f.b, f.a * s.l + f.b,
            (f.a * (s.l + s.r - 1) + f.b * 2) * (s.r - s.l) / 2, s.l, s.r};
}
F composition(F f, F g) { return f.a == LINF ? g : f; }
F id() { return {LINF, LINF}; }

using lazy_segtype =
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;

struct lazy_segtree_arithmetic : lazy_segtype {
  using lazy_segtype::lazy_segtype;
  lazy_segtree_arithmetic(int n) {
    vector<S> sv(n);
    for (int i = 0; i < n; i++) sv[i] = {0, 0, 0, i, i + 1};
    (*this) = lazy_segtree_arithmetic(sv);
  }
  lazy_segtree_arithmetic(vector<ll> v) {
    vector<S> sv(v.size());
    for (int i = 0; i < v.size(); i++) sv[i] = {v[i], v[i], v[i], i, i + 1};
    (*this) = lazy_segtree_arithmetic(sv);
  }
  // f = (a, b)
  // [l, r) を b, a+b, 2a+b, ... で更新
  void apply(int l, int r, F f) {
    lazy_segtype::apply(l, r, {f.a, f.b - f.a * get(l).l});
  }
  void apply(int p, F f) { apply(p, {f.a, f.b - f.a * get(p).l}); }
};
}  // namespace arithmetic

using namespace arithmetic;

Verify

ちょうどいい問題がなかったので作りました。

Range Arithmetic Query (easy) | MojaCoder

Range Arithmetic Query (hard) | MojaCoder

愚直解と照らし合わせているので変なバグはないと思われますが、おかしい点があればご一報ください。

'Range Arithmetic Query (hard)'のstoqさんの提出 | MojaCoder

使用例

ABC177-F I hate Shortest Path Problem

F - I hate Shortest Path Problem

これが解けなかったのがきっかけで作りました。貼るだけで解けます。

int main() {
  int h, w;
  cin >> h >> w;
  lazy_segtree_arithmetic seg(w);
  for (int i = 0; i < h; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    ll x = (l > 0 ? seg.get(l - 1).min : LINF);
    seg.apply(l, r, {1, x + 1});
    ll ans = seg.all_prod().min;
    cout << (ans >= LINF ? -1 : ans + i + 1) << "\n";
  }
}

Submission #25254062 - AtCoder Beginner Contest 177

他に使える問題を知っている方がいれば教えてください。

区間等差数列加算の遅延セグ木

関連して、区間に等差数列を足す遅延セグ木も考えられます。Min, Max の取得は難しいですが、総和は同様の考え方で実装できます。

using ll = long long;

// 区間sum & 区間等差加算
namespace arithmetic_add {

const ll LINF = ll(4e18);
const int INF = int(1e9) + 10;

struct S {
  ll sum;
  int l, r;
};
struct F {
  ll a, b;
};
S op(S s, S t) { return {s.sum + t.sum, min(s.l, t.l), max(s.r, t.r)}; }
S e() { return {0, INF, -INF}; }
S mapping(F f, S s) {
  return {s.sum + (f.a * (s.l + s.r - 1) + f.b * 2) * (s.r - s.l) / 2, s.l,
          s.r};
}
F composition(F f, F g) { return {f.a + g.a, f.b + g.b}; }
F id() { return {0, 0}; }

using lazy_segtype =
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;

struct lazy_segtree_arithmetic : lazy_segtype {
  using lazy_segtype::lazy_segtype;
  lazy_segtree_arithmetic(int n) {
    vector<S> sv(n);
    for (int i = 0; i < n; i++) sv[i] = {0, i, i + 1};
    (*this) = lazy_segtree_arithmetic(sv);
  }
  lazy_segtree_arithmetic(vector<ll> v) {
    vector<S> sv(v.size());
    for (int i = 0; i < v.size(); i++) sv[i] = {v[i], i, i + 1};
    (*this) = lazy_segtree_arithmetic(sv);
  }
  // f = (a, b)
  // [l, r) に b, a+b, 2a+b, ... を加算
  void apply(int l, int r, F f) {
    lazy_segtype::apply(l, r, {f.a, f.b - f.a * get(l).l});
  }
  void apply(int p, F f) { apply(p, {f.a, f.b - f.a * get(p).l}); }
};
}  // namespace arithmetic_add

using namespace arithmetic_add;

verify

HCPC2020 Day1 B - 三角形足し算

問題リンク：Aizu Online Judge Arena

提出：Aizu Online Judge Arena

参考文献

opt-cp.com