2D Fenwick Tree
(data-structure/fenwick_tree_2d.hpp)

• View this file on GitHub
• Last update: 2024-01-08 02:22:28+09:00
• Include: #include "data-structure/fenwick_tree_2d.hpp"

Code

#pragma once
#include <vector>

/**
 * @brief 2D Fenwick Tree
 */
template <typename T>
class FenwickTree2D {
   public:
    FenwickTree2D() = default;
    FenwickTree2D(int H, int W)
        : H(H), W(W), data(H + 1, std::vector<T>(W + 1)) {}

    void add(int a, int b, T x) {
        ++a;
        ++b;
        for (int i = a; i <= H; i += i & -i) {
            for (int j = b; j <= W; j += j & -j) {
                data[i][j] += x;
            }
        }
    }

    T sum(int a, int b) const {
        ++a;
        ++b;
        T ret = 0;
        for (int i = a; i > 0; i -= i & -i) {
            for (int j = b; j > 0; j -= j & -j) {
                ret += data[i][j];
            }
        }
        return ret;
    }

   private:
    int H, W;
    std::vector<std::vector<T>> data;
};

#line 2 "data-structure/fenwick_tree_2d.hpp"
#include <vector>

/**
 * @brief 2D Fenwick Tree
 */
template <typename T>
class FenwickTree2D {
   public:
    FenwickTree2D() = default;
    FenwickTree2D(int H, int W)
        : H(H), W(W), data(H + 1, std::vector<T>(W + 1)) {}

    void add(int a, int b, T x) {
        ++a;
        ++b;
        for (int i = a; i <= H; i += i & -i) {
            for (int j = b; j <= W; j += j & -j) {
                data[i][j] += x;
            }
        }
    }

    T sum(int a, int b) const {
        ++a;
        ++b;
        T ret = 0;
        for (int i = a; i > 0; i -= i & -i) {
            for (int j = b; j > 0; j -= j & -j) {
                ret += data[i][j];
            }
        }
        return ret;
    }

   private:
    int H, W;
    std::vector<std::vector<T>> data;
};

Back to top page