Binary Indexed Tree
(content/data_structures/bit.h)

• View this file on GitHub
• Last update: 2024-02-01 17:09:56-05:00

Reversable Functions

Standard BIT supports the following for reversable functions:

• point update + point query
• point update + range query
• range update + point query

To do range update + range query, use range_bit.

Non-reversable Functions

The only operations supported for non-reversable functions are:

• point update + prefix query
• suffix update + point query

Depends on

• My starter code (content/utils/template.h)

Verified with

• tests/bit.test.cpp

Code

#pragma once
#include "../utils/template.h"

/**
 * @brief Binary Indexed Tree
 * @docs docs/bit.md
 */

template<class T> struct bit{
	int SZ;
	vector<T> bit;
	function<T(T, T)> merge;
	
	void init(int n, T def, function<T(T, T)> f){
		SZ = n;
		bit.resize(SZ, def);
		merge = f;
	}
	void update(int i, T v){
		for(; i < SZ; i += i&-i)
			bit[i] = merge(bit[i], v);
	}
	T query(int i){
		T x = bit[0];
		for(; i; i -= i&-i)
			x = merge(x, bit[i]);
		return x;
	}
};

template<class T> struct range_bit{
	bit<T> T1, T2;
	function<T(T, T)> unmerge;

	void init(int n, T def, function<T(T, T)> f, function<T(T, T)> g){
		T1.init(n, def, f);
		T2.init(n, def, f);
		unmerge = g;
	}
	T query(int i){
		return i*T1.query(i)-T2.query(i);
	}
	T query(int l, int r){
		return unmerge(query(r), query(l-1));
	}
	void update(int l, int r, T v){
		T1.update(l, v);
		T1.update(r+1, -v);
		T2.update(l, v*(l-1));
		T2.update(r+1, -v*r);
	}
	void update(int l, T v){
		update(l, l, v);
	}
};

#line 1 "content/utils/template.h"
/**
 * @brief My starter code
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end());

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#line 3 "content/data_structures/bit.h"

/**
 * @brief Binary Indexed Tree
 * @docs docs/bit.md
 */

template<class T> struct bit{
	int SZ;
	vector<T> bit;
	function<T(T, T)> merge;
	
	void init(int n, T def, function<T(T, T)> f){
		SZ = n;
		bit.resize(SZ, def);
		merge = f;
	}
	void update(int i, T v){
		for(; i < SZ; i += i&-i)
			bit[i] = merge(bit[i], v);
	}
	T query(int i){
		T x = bit[0];
		for(; i; i -= i&-i)
			x = merge(x, bit[i]);
		return x;
	}
};

template<class T> struct range_bit{
	bit<T> T1, T2;
	function<T(T, T)> unmerge;

	void init(int n, T def, function<T(T, T)> f, function<T(T, T)> g){
		T1.init(n, def, f);
		T2.init(n, def, f);
		unmerge = g;
	}
	T query(int i){
		return i*T1.query(i)-T2.query(i);
	}
	T query(int l, int r){
		return unmerge(query(r), query(l-1));
	}
	void update(int l, int r, T v){
		T1.update(l, v);
		T1.update(r+1, -v);
		T2.update(l, v*(l-1));
		T2.update(r+1, -v*r);
	}
	void update(int l, T v){
		update(l, l, v);
	}
};

Back to top page