mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

BIT(Binary Indexed Tree)
(data_structure/binary_indexed_tree.hpp)

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

BIT(Binary Indexed Tree)

使い方

• 要素数を $N$ とする
• binary_indexed_tree<T>(int n) : 要素数 $N$ の BIT を構築する
• add(int i, T x) : $i$ 番目に $x$ を加算する $O(\log(N))$
• sum(int i) : $[1, i]$ の総和を求める $O(\log(N))$

Verified with

• verify/aoj/dsl/2_B___BIT.test.cpp
• verify/aoj/dsl/2_E___BIT.test.cpp

Code

#pragma once

#include<cassert>
#include<vector>

template<typename T>struct binary_indexed_tree {
	int n;
	std::vector<T> BIT;
	binary_indexed_tree(int n_) : n(n_ + 1), BIT(n, 0) {}

	void add(int i, T x){
		assert(1 <= i && i <= n);
		for(int idx = i;idx < n;idx += (idx & -idx)){
			BIT[idx] += x;
		}
	}
	
	T sum(int i) {
		assert(1 <= i && i <= n);
		T ret = 0;
		for(int idx = i;idx > 0;idx -= (idx & -idx)){
			ret += BIT[idx];
		}
		return ret;
	}
};

#line 2 "data_structure/binary_indexed_tree.hpp"

#include<cassert>
#include<vector>

template<typename T>struct binary_indexed_tree {
	int n;
	std::vector<T> BIT;
	binary_indexed_tree(int n_) : n(n_ + 1), BIT(n, 0) {}

	void add(int i, T x){
		assert(1 <= i && i <= n);
		for(int idx = i;idx < n;idx += (idx & -idx)){
			BIT[idx] += x;
		}
	}
	
	T sum(int i) {
		assert(1 <= i && i <= n);
		T ret = 0;
		for(int idx = i;idx > 0;idx -= (idx & -idx)){
			ret += BIT[idx];
		}
		return ret;
	}
};

Back to top page