Fenwick Tree Prefix
(library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp)

• View this file on GitHub
• Last update: 2022-06-14 00:04:21+09:00
• Include: #include "library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp"

Fenwick Tree Prefix

一般のモノイド $(\oplus,M)$ が乗る代わりに，処理できるクエリは以下の 2 つに制限される．

• $\mathrm{apply}(i,v)$: $A _ i \leftarrow A _ i \oplus v$ と更新する
• $\mathrm{prefix\_query}(r)$: $\displaystyle \bigoplus _ {i = 0} ^ {r - 1} A _ i$ を計算する

Required by

• マンハッタン距離で最も近い点への距離の列挙 (library/graph/manhattan_minimum_distances.hpp)
• Manhattan Mst (library/graph/manhattan_mst.hpp)

Verified with

• test/src/graph/manhattan_mst/manhattanmst.test.cpp

Code

#ifndef SUISEN_FENWICK_TREE_PREFIX
#define SUISEN_FENWICK_TREE_PREFIX

#include <vector>

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)()>
    struct FenwickTreePrefix {
        FenwickTreePrefix() : FenwickTreePrefix(0) {}
        explicit FenwickTreePrefix(int n) : _n(n), _dat(_n + 1, e()) {}
        FenwickTreePrefix(const std::vector<T> &dat) : _n(dat.size()), _dat(_n + 1, e()) {
            for (int i = _n; i > 0; --i) {
                _dat[i] = op(_dat[i], dat[i - 1]);
                if (int p = i + (-i & i); p <= _n) _dat[p] = op(_dat[p], _dat[i]);
            }
        }
        void apply(int i, const T& val) {
            for (++i; i <= _n; i += -i & i) _dat[i] = op(_dat[i], val);
        }
        T prefix_query(int r) const {
            T res = e();
            for (; r; r -= -r & r) res = op(res, _dat[r]);
            return res;
        }
    private:
        int _n;
        std::vector<T> _dat;
    };
} // namespace suisen


#endif // SUISEN_FENWICK_TREE_PREFIX

#line 1 "library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp"



#include <vector>

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)()>
    struct FenwickTreePrefix {
        FenwickTreePrefix() : FenwickTreePrefix(0) {}
        explicit FenwickTreePrefix(int n) : _n(n), _dat(_n + 1, e()) {}
        FenwickTreePrefix(const std::vector<T> &dat) : _n(dat.size()), _dat(_n + 1, e()) {
            for (int i = _n; i > 0; --i) {
                _dat[i] = op(_dat[i], dat[i - 1]);
                if (int p = i + (-i & i); p <= _n) _dat[p] = op(_dat[p], _dat[i]);
            }
        }
        void apply(int i, const T& val) {
            for (++i; i <= _n; i += -i & i) _dat[i] = op(_dat[i], val);
        }
        T prefix_query(int r) const {
            T res = e();
            for (; r; r -= -r & r) res = op(res, _dat[r]);
            return res;
        }
    private:
        int _n;
        std::vector<T> _dat;
    };
} // namespace suisen

Back to top page