データアクセスに制限のある Binary Indexed Tree () の高速化

タイトルについて

正しくは「データアクセスに制限のある Binary Indexed Tree (と同じクエリに答えるデータ構造) の高速化」です

Binary Indexed Tree とは

以下のクエリに時間O(logN)で答えることが出来るデータ構造．

初期化

• サイズNの配列の要素を0に初期化する．

応答

• add(ptr, val) ptr番目の要素にvalを加算
• sum(ptr) 要素[1..ptr]の総和を求める

本記事で加える制約

• データ構造は「カーソル」を持つ．
• カーソルは1つ右，または1つ左へ移動できる．
• 1番目からカーソル位置までの総和を求める

この場合，addとsumを時間O(1)で答えることが出来る．

実装

カーソルと一緒に累積和の情報を持っておくと，簡単に出来てしまう．

struct BitreeL {
    using value_type = int;
    vector<value_type> data_;

    int ptr_ = 0;
    value_type sum_ = 0;

    BitreeL(int _size):data_(_size) {}

    // カーソル位置(!!0indexed!!)
    inline int cursor() const {
        return ptr_;
    }

    // 先頭から現在のカーソル位置までの要素の総和を取る．
    inline value_type sum() const {
        return sum_;
    }

    // 現在のカーソル位置の要素に_valを加算する
    inline void add(value_type _val) {
        data_[ptr_] += _val;
        sum_ += _val;
    }

    // idx番目の要素に_valを加算する(!!0indexed!!)
    inline void add(int _idx, value_type _val) {
        data_[_idx] += _val;
        if (_idx <= ptr_)
            sum_ += _val;
    }

    // カーソルを増加させる(例外処理なし)
    inline void increment() {
        sum_ += data_[++ptr_];
    }
    // カーソルを減少させる(例外処理なし)
    inline void decrement() {
        sum_ -= data_[ptr_--];
    }
};

データ構造がカーソルを持つとか，それ何処のkuinですか？という話になる．

しかし，データ構造とカーソルを別のstructで実装すると，addを呼び出したときにカーソル側の累積和を書き換える必要がある．

よって，全単射にならざるを得なくなり，だったらくっつけちゃえばいいよねという根拠です．

おまけ

value_type型のフィールド1つを追加すれば，「カーソル位置から末尾までの総和」も 時間O(1) で計算できる．