Implementations

C++

#include <concepts>
#include <cstddef>
#include <vector>
 
template <typename T>
concept Group = requires(T a, T b) {
	// INFO: you need to use other std::concepts in rhs here
	// so can't do std::is_same_v, need std::is_same_as
	// alternative is to add another row that does a
	// requires is_same_v<decltype(a + b), T>;
	{ a - b } -> std::same_as<T>;
	{ a + b } -> std::same_as<T>;
	{ T{} } -> std::same_as<T>; // identity
};
 
template <Group T> class FenwickTree {
  private:
	std::vector<T> ft_, array_;
 
  public:
	FenwickTree(std::size_t size) : array_(size), ft_(size + 1) {}
 
	FenwickTree(const std::vector<T> &array) : array_(array), ft_(array_.size() + 1) {
		// what we do is update the range THIS element belongs to
		// and also the range that would be ONE higher for this range
		// so that when we go from left to right, we keep on accumulating
 
		for (std::size_t i = 1; i < ft_.size(); i++) {
			// note the add, this is to acucmulate for any forward
			// done changes
			ft_[i] += array[i - 1];
			auto next = i + (i & -i);
			if (next < ft_.size())
				ft_[next] += ft_[i];
		}
	}
 
	void add(std::size_t i, T val) {
		array_[i] += val;
		for (++i; i < ft_.size(); i += i & -i)
			ft_[i] += val;
	}
 
    // WARN: i was initially thinking of returning T& here hoping that
    // language will manage it for me but that's just plain wrong, think
    // about it
	T sum(std::size_t i) const {
		T ret{};
		for (++i; i > 0; i -= i & -i)
			ret += ft_[i];
		return ret;
	}
 
	void set(std::size_t i, T val) {
		T delta = val - array_[i];
		add(i, delta);
	}
};

Java

 
// java has no way to do generics like FenwickTree<T extends Number>
// that's JUST not possible, what is an alternative is to define an
// interface say GroupOps<T> and pass that to the ctor and have
// add, sub etc defined there
final class FenwickTree {
    private int[] array;
    private int[] ft;
 
    public FenwickTree(int size) {
        array = new int[size];
        ft = new int[size + 1];
    }
 
    public FenwickTree(int[] array) {
        this.array = array.clone();
        ft = new int[array.length + 1];
 
        for (int i = 1; i < ft.length; i++) {
            ft[i] += array[i - 1];
 
            int next = i + (i & -i);
            if (next < ft.length) {
                ft[next] += ft[i];
            }
        }
    }
 
    // INFO: rem [] style arrays have .length not size() or size
 
    public void add(int i, int val) {
        array[i] += val;
        for (++i; i < ft.length; i += i & -i) {
            ft[i] += val;
        }
    }
 
    public int sum(int i) {
        int res = 0;
        for (++i; i > 0; i -= i & -i) {
            res += ft[i];
        }
        return res;
    }
 
    public void set(int i, int val) {
        int delta = val - array[i];
        add(i, delta);
    }
}

Notes

Core

monoids

Defn

set S
bin op x st S x S → S ⇒ read as combines two

SUCH THAT

closure ( a x b belongs to S for both a,b in S )
associative ⇒ bracket can move
there is an e in S st for all a x e = a

in fenwick trees?

the type T being a monoid is enough for point updates and prefix ops.

then T needs an inverse for every element ( note that even ranges are covered because ranges are reduction of multiple Ts to one and being a monoid that single element reduction also exists in T )

monoid + inverse = group

so for arbitrary prefix sums you need T to be a group

enforcing this in languages?

we can require them to have certain ops like + or - in cpp or a combine or similar funcs but not really the behavior so then is kind of pointless

Remember

https://cp-algorithms.com/data_structures/binary_indexed_tree.png

An element x, is part of ranges that are stored at HIGHER indexes. So when updating you also need to update those higher indexes.

The reverse holds when querying.

To remember, consider a case of quering a range as some prefix + the immediate element, CLEARLY you need to decrease in indexes.

ALSO, a set is done via a delta update. No way around it.

java

autounboxing

allows Integer ←> int conversion
backed into the language, you cannot add them for your custom types

Lest I Forget

Fenwick Tree