Fenwick Tree (Binary Indexed Tree)
(ds/range_query/fenwick_tree.hpp)

• View this file on GitHub
• Last update: 2026-06-27 04:10:54+09:00
• Include: #include "ds/range_query/fenwick_tree.hpp"

Overview

A Fenwick tree, also called a binary indexed tree, supports point additions and prefix-sum queries in logarithmic time.

Indices are zero-based and range queries use half-open intervals [l, r).

Template Parameters

• T: The underlying numeric type of the elements (e.g., int, long long, or a modular integer modint).

Methods

Method	Description	Complexity
FenwickTree(int n)	Initializes an array of size n with 0s.	$O(N)$
FenwickTree(const std::vector<T>& a)	Builds a tree from a given vector array a.	$O(N)$
int size() const	Returns the number of elements.	$O(1)$
bool empty() const	Returns whether the tree is empty.	$O(1)$
void add(int p, const T& x)	Adds x to the element at index p.	$O(\log N)$
T sum(int r) const	Returns the sum of elements in the prefix [0, r).	$O(\log N)$
T sum(int l, int r) const	Returns the sum of elements in the interval [l, r).	$O(\log N)$
int lower_bound(T w) const	Returns the minimum r such that sum(r) >= w. Returns 0 when w <= 0 and size() + 1 when no such prefix exists. All values must be non-negative.	$O(\log N)$

Example

#include "ds/range_query/fenwick_tree.hpp"
#include <iostream>
#include <vector>

int main() {
    std::vector<long long> a = {1, 2, 3, 4, 5};
    m1une::ds::FenwickTree<long long> tree(a);

    // Sum of [1, 4) which is elements at index 1, 2, 3 (2 + 3 + 4 = 9)
    std::cout << tree.sum(1, 4) << "\n"; // Output: 9

    // Add 10 to index 2
    tree.add(2, 10); // Array logically becomes: 1, 2, 13, 4, 5

    // Re-query the sum
    std::cout << tree.sum(1, 4) << "\n"; // Output: 19

    // Find the smallest prefix whose sum is >= 15
    // prefix [0, 3) = 1 + 2 + 13 = 16
    std::cout << tree.lower_bound(15) << "\n"; // Output: 3

    return 0;
}

Required by

• Offline Rectangle Add Rectangle Sum (ds/range_query/offline_rectangle_add_rectangle_sum.hpp)
• Geometry Bundle (geometry/all.hpp)
• Manhattan Segment Intersections (geometry/manhattan_segment_intersections.hpp)

Verified with

• verify/algo/offline/mo.test.cpp
• verify/ds/range_query/fenwick_tree.test.cpp
• verify/ds/range_query/offline_rectangle_add_rectangle_sum.test.cpp
• verify/geometry/centroid.test.cpp
• verify/geometry/geometry_algorithms.test.cpp
• verify/geometry/manhattan_segment_intersections.test.cpp
• verify/geometry/rational.test.cpp
• verify/graph/tree/vertex_add_subtree_sum.test.cpp

Code

#ifndef M1UNE_DS_FENWICK_TREE_HPP
#define M1UNE_DS_FENWICK_TREE_HPP 1

#include <cassert>
#include <vector>

namespace m1une {
namespace ds {

template <typename T>
struct FenwickTree {
   private:
    int _n;
    int _max_power;
    std::vector<T> _data;

    static int max_power_leq(int n) {
        int result = 1;
        while (result <= n / 2) result <<= 1;
        return result;
    }

    T prefix_sum(int r) const {
        T result{};
        const T* data = _data.data();
        while (r > 0) {
            result += data[r];
            r -= r & -r;
        }
        return result;
    }

   public:
    FenwickTree() : _n(0), _max_power(0) {}

    explicit FenwickTree(int n)
        : _n(n), _max_power(max_power_leq(n > 0 ? n : 1)), _data(n + 1, T{}) {}

    explicit FenwickTree(const std::vector<T>& a)
        : _n(int(a.size())),
          _max_power(max_power_leq(_n > 0 ? _n : 1)),
          _data(a.size() + 1, T{}) {
        for (int i = 1; i <= _n; ++i) {
            _data[i] += a[i - 1];
            const int p = i + (i & -i);
            if (p <= _n) {
                _data[p] += _data[i];
            }
        }
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    // Adds `x` to the element at zero-based index `p`.
    void add(int p, const T& x) {
        assert(0 <= p && p < _n);
        ++p;
        T* data = _data.data();
        while (p <= _n) {
            data[p] += x;
            p += p & -p;
        }
    }

    // Returns the sum of elements in the range [0, r).
    T sum(int r) const {
        assert(0 <= r && r <= _n);
        return prefix_sum(r);
    }

    // Returns the sum of elements in the range [l, r).
    T sum(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        return prefix_sum(r) - prefix_sum(l);
    }

    // Returns the minimum index `r` such that the sum of [0, r) >= w.
    // Requires all elements in the tree to be non-negative.
    int lower_bound(T w) const {
        if (w <= 0) return 0;
        int x = 0;
        const T* data = _data.data();
        for (int k = _max_power; k > 0; k >>= 1) {
            if (x + k <= _n && data[x + k] < w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x + 1;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_FENWICK_TREE_HPP

#line 1 "ds/range_query/fenwick_tree.hpp"



#include <cassert>
#include <vector>

namespace m1une {
namespace ds {

template <typename T>
struct FenwickTree {
   private:
    int _n;
    int _max_power;
    std::vector<T> _data;

    static int max_power_leq(int n) {
        int result = 1;
        while (result <= n / 2) result <<= 1;
        return result;
    }

    T prefix_sum(int r) const {
        T result{};
        const T* data = _data.data();
        while (r > 0) {
            result += data[r];
            r -= r & -r;
        }
        return result;
    }

   public:
    FenwickTree() : _n(0), _max_power(0) {}

    explicit FenwickTree(int n)
        : _n(n), _max_power(max_power_leq(n > 0 ? n : 1)), _data(n + 1, T{}) {}

    explicit FenwickTree(const std::vector<T>& a)
        : _n(int(a.size())),
          _max_power(max_power_leq(_n > 0 ? _n : 1)),
          _data(a.size() + 1, T{}) {
        for (int i = 1; i <= _n; ++i) {
            _data[i] += a[i - 1];
            const int p = i + (i & -i);
            if (p <= _n) {
                _data[p] += _data[i];
            }
        }
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    // Adds `x` to the element at zero-based index `p`.
    void add(int p, const T& x) {
        assert(0 <= p && p < _n);
        ++p;
        T* data = _data.data();
        while (p <= _n) {
            data[p] += x;
            p += p & -p;
        }
    }

    // Returns the sum of elements in the range [0, r).
    T sum(int r) const {
        assert(0 <= r && r <= _n);
        return prefix_sum(r);
    }

    // Returns the sum of elements in the range [l, r).
    T sum(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        return prefix_sum(r) - prefix_sum(l);
    }

    // Returns the minimum index `r` such that the sum of [0, r) >= w.
    // Requires all elements in the tree to be non-negative.
    int lower_bound(T w) const {
        if (w <= 0) return 0;
        int x = 0;
        const T* data = _data.data();
        for (int k = _max_power; k > 0; k >>= 1) {
            if (x + k <= _n && data[x + k] < w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x + 1;
    }
};

}  // namespace ds
}  // namespace m1une

Back to top page