Fenwick Tree (Binary Indexed Tree) (src/datastructure/fenwick_tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-11-03 14:10:53+09:00
• Include: #include "src/datastructure/fenwick_tree.hpp"

Required by

• 転倒数 (src/vector/inversion_number.hpp)

Verified with

• test/datastructure/fenwick_tree/aoj_dsl_2_b.test.cpp
• test/vector/inversion_number/aoj_alds1_5_d.test.cpp

Code

#ifndef DATASTRUCTURE_FENWICK_TREE
#define DATASTRUCTURE_FENWICK_TREE

#include <vector>

template<class T>
class FenwickTree {
private:
	int n;
	std::vector<T> tree;

public:
	FenwickTree(int n) : n(n), tree(n) {}

	void add(int i, T x) {
		++i;
		while (i <= n) {
			tree[i - 1] += x;
			i += i & -i;
		}
	}

	T sum(int i) { // [0, i)
		T s{0};
		while (i > 0) {
			s += tree[i - 1];
			i -= i & -i;
		}
		return s;
	}

	T find(int l, int r) { // [l, r)
		return sum(r) - sum(l);
	}
};

#endif // DATASTRUCTURE_FENWICK_TREE

#line 1 "src/datastructure/fenwick_tree.hpp"



#include <vector>

template<class T>
class FenwickTree {
private:
	int n;
	std::vector<T> tree;

public:
	FenwickTree(int n) : n(n), tree(n) {}

	void add(int i, T x) {
		++i;
		while (i <= n) {
			tree[i - 1] += x;
			i += i & -i;
		}
	}

	T sum(int i) { // [0, i)
		T s{0};
		while (i > 0) {
			s += tree[i - 1];
			i -= i & -i;
		}
		return s;
	}

	T find(int l, int r) { // [l, r)
		return sum(r) - sum(l);
	}
};

Back to top page