2次元セグメント木
(Datastructure/2dsegtree.hpp)

• View this file on GitHub
• Last update: 2024-07-06 20:37:29+09:00
• Include: #include "Datastructure/2dsegtree.hpp"

概要

2dセグ木

コンストラクタ

segtree2d<S, op, e>(int h, int w) … [0, h) * [0, w)のグリッドを作る。半開区間

• 計算量 $O(HW)$

関数

• void preset(int y, int x, S v) … A[y][x] = v
  • 計算量 $O(1)$
• void build() … 2dセグ木を構築する。presetをしなかった場合は必要ない。
  • 計算量 $O(HW)$
• void set(int y, int x, S v) … A[y][x] = v
  • 計算量 $O(\log{H} \log{W})$
  • 制約 presetをした場合、setを呼ぶ前にbuildを呼ぶ。そうでない場合、assertでbool変数 fが反応する。
• S prod(int sy, int ty, int sx, int tx) … [sy, sx) * [ty, tx)の矩形領域の和を返す。半開区間
  • 計算量 $O(\log{H} \log{W})$
  • 制約 presetをした場合、setを呼ぶ前にbuildを呼ぶ。そうでない場合、assertでbool変数 fが反応する。

pro tips

• 加算の時 2dBITで良い。

• imos法 累積和の取り方について imos法について、加算場所は一意には定まらない。よって、マイナスの座標を含まないように、右上の法に加算すると都合が良い。

実装について

2次元配列を1次元配列に直すような実装(参考 : https://nyaannyaan.github.io/library/data-structure-2d/2d-segment-tree.hpp.html)

1次元に直さない場合、 H = 10 ^ 6, W = 1のような極端なケースでのMLEを対策する必要が出る場合がある。参考: vector自体のメモリ使用量

Verified with

• verify/Datastructure_2dsegtree_add.test.cpp
• verify/Datastructure_2dsegtree_max.test.cpp

Code

template <class S, S (*op)(S, S), S (*e)()> struct segtree2d {
    int id(int y, int x) {return y * 2 * W + x;} //= y番目のセグ木の、ノードxに対応する添字
    int H, W;
    vec<S> dat;
    bool f;

    segtree2d(int h, int w) {
        f = true;
        H = W = 1;
        while(H < h) H <<= 1;
        while(W < w) W <<= 1;
        dat.resize(4 * H * W, e());
    }

    void preset(int y, int x, S v) {f = false,  dat[id(y + H, x + W)] = v; }

    void build() {
        f = true;
        rep(h, H, 2 * H) {
            rrep(w, 1, W) {
                dat[id(h, w)] = op(dat[id(h, 2 * w)], dat[id(h, 2 * w + 1)]);
            }
        }
        
        rrep(h, 0, H) {
            rrep(w, 1, 2 * W) {
                dat[id(h, w)] = op(dat[id(h * 2, w)], dat[id(h * 2 + 1, w)]);
            } 
        }
    }

    void set(int y, int x, S v) {
        assert(f);

        y += H, x += W;
        dat[id(y, x)] = v;
        rrep(w, 1, W) {
            dat[id(y, w)] = op(dat[id(y, 2 * w)], dat[id(y, 2 * w + 1)]);
        }

        while(y > 1) {
            y >>= 1;
            for(int j = x; j >= 1; j >>= 1) {
                dat[id(y, j)] = op(dat[id(y * 2, j)] , dat[id(y * 2 + 1, j)]);
            }
        }
    }

    S inner(int h, int l, int r) {
        S sml = e(), smr = e();
        l += W, r += W;
        while(l < r) {
            if(l & 1) sml = op(sml, dat[id(h, l++)]);
            if(r & 1) smr = op(dat[id(h, --r)], smr);
            l >>= 1, r >>= 1;
        }
        return op(sml, smr);
    }

    S prod(int sy, int ty, int sx, int tx) {
        assert(f);

        S sml = e(), smr = e();
        sy += H, ty += H;
        while(sy < ty) {
            if(sy & 1) sml = op(sml, inner(sy++, sx, tx));
            if(ty & 1) smr = op(inner(--ty, sx, tx), smr);
            sy >>= 1, ty >>= 1;
        }
        return op(sml, smr);
    }

    S get(int y, int x) {
        return dat[id(y + H, x + W)];
    }
};
/*
@brief 2次元セグメント木
@docs doc/2dseg_small.md
*/

#line 1 "Datastructure/2dsegtree.hpp"
template <class S, S (*op)(S, S), S (*e)()> struct segtree2d {
    int id(int y, int x) {return y * 2 * W + x;} //= y番目のセグ木の、ノードxに対応する添字
    int H, W;
    vec<S> dat;
    bool f;

    segtree2d(int h, int w) {
        f = true;
        H = W = 1;
        while(H < h) H <<= 1;
        while(W < w) W <<= 1;
        dat.resize(4 * H * W, e());
    }

    void preset(int y, int x, S v) {f = false,  dat[id(y + H, x + W)] = v; }

    void build() {
        f = true;
        rep(h, H, 2 * H) {
            rrep(w, 1, W) {
                dat[id(h, w)] = op(dat[id(h, 2 * w)], dat[id(h, 2 * w + 1)]);
            }
        }
        
        rrep(h, 0, H) {
            rrep(w, 1, 2 * W) {
                dat[id(h, w)] = op(dat[id(h * 2, w)], dat[id(h * 2 + 1, w)]);
            } 
        }
    }

    void set(int y, int x, S v) {
        assert(f);

        y += H, x += W;
        dat[id(y, x)] = v;
        rrep(w, 1, W) {
            dat[id(y, w)] = op(dat[id(y, 2 * w)], dat[id(y, 2 * w + 1)]);
        }

        while(y > 1) {
            y >>= 1;
            for(int j = x; j >= 1; j >>= 1) {
                dat[id(y, j)] = op(dat[id(y * 2, j)] , dat[id(y * 2 + 1, j)]);
            }
        }
    }

    S inner(int h, int l, int r) {
        S sml = e(), smr = e();
        l += W, r += W;
        while(l < r) {
            if(l & 1) sml = op(sml, dat[id(h, l++)]);
            if(r & 1) smr = op(dat[id(h, --r)], smr);
            l >>= 1, r >>= 1;
        }
        return op(sml, smr);
    }

    S prod(int sy, int ty, int sx, int tx) {
        assert(f);

        S sml = e(), smr = e();
        sy += H, ty += H;
        while(sy < ty) {
            if(sy & 1) sml = op(sml, inner(sy++, sx, tx));
            if(ty & 1) smr = op(inner(--ty, sx, tx), smr);
            sy >>= 1, ty >>= 1;
        }
        return op(sml, smr);
    }

    S get(int y, int x) {
        return dat[id(y + H, x + W)];
    }
};
/*
@brief 2次元セグメント木
@docs doc/2dseg_small.md
*/

Back to top page