data_structure/binary_indexed_tree.hpp

• View this file on GitHub
• Last update: 2025-01-05 04:43:56+09:00
• Include: #include "data_structure/binary_indexed_tree.hpp"

Verified with

• verify/yosupo_ds/ds_point_add_range_sum_2.test.cpp
• verify/yosupo_ds/ds_static_range_inversions.test.cpp

Code

#ifndef KK2_DATA_STRUCTURE_BINARY_INDEXED_TREE_HPP
#define KK2_DATA_STRUCTURE_BINARY_INDEXED_TREE_HPP 1

#include <cassert>
#include <vector>

namespace kk2 {

template <typename T> struct BinaryIndexedTree {
    BinaryIndexedTree() : _n(0) {}

    BinaryIndexedTree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        for (p++; p <= _n; p += p & -p) data[p - 1] += x;
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

    T get(int p) {
        assert(0 <= p && p < _n);
        return sum(p + 1) - sum(p);
    }

  private:
    int _n;
    std::vector<T> data;

    T sum(int r) {
        T s{};
        for (; r > 0; r -= r & -r) s += data[r - 1];
        return s;
    }
};

} // namespace kk2

#endif // #ifndef KK2_DATA_STRUCTURE_BINARY_INDEXED_TREE_HPP

#line 1 "data_structure/binary_indexed_tree.hpp"



#include <cassert>
#include <vector>

namespace kk2 {

template <typename T> struct BinaryIndexedTree {
    BinaryIndexedTree() : _n(0) {}

    BinaryIndexedTree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        for (p++; p <= _n; p += p & -p) data[p - 1] += x;
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

    T get(int p) {
        assert(0 <= p && p < _n);
        return sum(p + 1) - sum(p);
    }

  private:
    int _n;
    std::vector<T> data;

    T sum(int r) {
        T s{};
        for (; r > 0; r -= r & -r) s += data[r - 1];
        return s;
    }
};

} // namespace kk2

Back to top page