// Taken from
// https://kartikkukreja.wordpress.com/2013/05/11/bit-fenwick-tree-data-structure-c-implementation/
// Has MIT licence
// Slightly modified
#pragma once

#define LSOne(S) (S & (-S))

template <typename T>
class BIT {
	T* ft;
    size_t size;
public:
	// initialize a BIT of n elements to zero
	BIT(size_t n) {
		size = n;
		ft = new T[n+1](); // () sets it to zero
	}

	~BIT()	{
		delete [] ft;
	}

	// returns sum of the range [1...b]
	T sum(size_t b) {
		T sum = 0;
		for (; b; b -= LSOne(b)) sum += ft[b];
		return sum;
	}

	// returns sum of the range [a...b]
	T sum(size_t a, size_t b) {
		return sum(b) - (a == 1 ? 0 : sum(a - 1));
	}

	// update value of the k-th element by v (v can be +ve/inc or -ve/dec)
	// i.e., increment or decrement kth element by a value v
	void update(size_t k, T v) {
		for (; k <= size; k += LSOne(k)) ft[k] += v;
	}

    // divide each original frequency by c
	void scaleDown(T c){
        for (int i=1 ; i<=size ; i++) ft[i] /= c;
    }

    // multiply each original frequency by c
    void scaleUp(T c){
        for (int i=1 ; i<=size ; i++) ft[i] *= c;
    }
};