Dual Binary Indexed Tree
(data-structure/binary-indexed-tree/DualBinaryIndexedTree.hpp)

• View this file on GitHub
• Last update: 2025-05-03 16:54:49+09:00
• Include: #include "data-structure/binary-indexed-tree/DualBinaryIndexedTree.hpp"

概要

todo

計算量

todo

Required by

• Wavelet Matrix (Dual BIT) (data-structure/wavelet-matrix/WaveletMatrixDualBinaryIndexedTree.hpp)
• Rectangle Add Point Get (data-structure/wavelet-matrix/rectangle/RectangleAddPointGet.hpp)
• Centroid Decomposition (Contour Add) (graph/tree/CentroidDecompositionContourAdd.hpp)

Verified with

• verify/LibraryChecker/tree/VertexGetRangeContourAddonTree.test.cpp

Code

template <class T>
struct RangeAddPointGet {
   private:
    fenwick_tree<T> ft;

   public:
    RangeAddPointGet() {}
    RangeAddPointGet(int siz) : ft(siz + 1) {}

    void range_add(int l, int r, T x) {
        ft.add(l, x);
        ft.add(r, -x);
    }

    void add(int p, T x) {
        ft.add(p, x);
        ft.add(p + 1, -x);
    }

    T point_get(int p) {
        return ft.sum(0, p + 1);
    }
};

#line 1 "data-structure/binary-indexed-tree/DualBinaryIndexedTree.hpp"
template <class T>
struct RangeAddPointGet {
   private:
    fenwick_tree<T> ft;

   public:
    RangeAddPointGet() {}
    RangeAddPointGet(int siz) : ft(siz + 1) {}

    void range_add(int l, int r, T x) {
        ft.add(l, x);
        ft.add(r, -x);
    }

    void add(int p, T x) {
        ft.add(p, x);
        ft.add(p + 1, -x);
    }

    T point_get(int p) {
        return ft.sum(0, p + 1);
    }
};

Back to top page