General Fenwick Tree
(library/data-structures/2d-range-queries/general-fenwick-tree.hpp)

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Include: #include "library/data-structures/2d-range-queries/general-fenwick-tree.hpp"

General Fenwick Tree

Multidimensional Fenwick Tree.

Assumptions

• $1$-indexed.

Functions

• upd(pos, ...): Update at location of coordinates in $\mathcal O(\log(n)^d).
• query(l, r, ...): Query in “rectangular” region in $\mathcal O(\log(n)^d).

Resources

• Benq

Verified with

• verify/codeforces/codeforces-869E-general-fwt.test.cpp

Code

#pragma once

constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); } 

template <class T, int ...Ns> struct BIT {
	T val = 0; void upd(T v) { val += v; }
	T query() { return val; }
};

template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
	BIT<T, Ns...> bit[N + 1];

	template <typename... Args> void upd(int pos, Args... args) { 
		assert(pos > 0);
		for (; pos <= N; pos += pos & -pos) 
			bit[pos].upd(args...); 
	}

	template <typename... Args> T sum(int r, Args... args) {
		T res = 0; 
		for (; r; r -= r & -r) 
			res += bit[r].query(args...); 
		return res; 
	}

	template <typename... Args> T query(int l, int r, Args... args) { 
		return sum(r, args...) - sum(l - 1, args...); 
	}

	int get_kth(T des) { 
		assert(des > 0);
		int ind = 0;
		for (int i = 1 << bits(N); i; i /= 2)
			if (ind + i <= N && bit[ind + i].val < des)
				des -= bit[ind += i].val;
		assert(ind < N); return ind + 1;
	}
}; 

constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); } 

template <class T, int ...Ns> struct BIT {
	T val = 0; void upd(T v) { val += v; }
	T query() { return val; }
};

template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
	BIT<T, Ns...> bit[N + 1];

	template <typename... Args> void upd(int pos, Args... args) { 
		assert(pos > 0);
		for (; pos <= N; pos += pos & -pos) 
			bit[pos].upd(args...); 
	}

	template <typename... Args> T sum(int r, Args... args) {
		T res = 0; 
		for (; r; r -= r & -r) 
			res += bit[r].query(args...); 
		return res; 
	}

	template <typename... Args> T query(int l, int r, Args... args) { 
		return sum(r, args...) - sum(l - 1, args...); 
	}

	int get_kth(T des) { 
		assert(des > 0);
		int ind = 0;
		for (int i = 1 << bits(N); i; i /= 2)
			if (ind + i <= N && bit[ind + i].val < des)
				des -= bit[ind += i].val;
		assert(ind < N); return ind + 1;
	}
}; 

Back to top page