NyaaLIB::DS_NyaaBIT

BIT (Binary Indexed Tree)　要素加算 、区間総和取得
https://atcoder.github.io/ac-library/production/document_ja/fenwicktree.html
Fenwick Tree とも呼ばれる。遅延セグ木の下位互換だが、遅延セグ木に比べて定数倍高速に動作する。

namespace NyaaLIB
{
	/**
	* BIT(Binary Indexed Tree)ライブラリ
	* 要素加算: O(log N)
	* 区間取得: O(log N)
	**/

	template <class T = int64_t> struct DS_NyaaBIT
	{   // Binary Indexed Tree (Fenwick Tree)
	public:
		using ll = int64_t;
		// data[0]からdata[N-1]の領域を確保する
		DS_NyaaBIT() : N(0), data(0) {}
		DS_NyaaBIT(ll N) : N(N), data(N) {}
		void Add(ll p, T x)
		{ // data[p]にxを加算する
			assert(0 <= p && p < N), p++;
			while (p <= N) data[p - 1] += x, p += p & -p;
		}
		// data[0]からdata[N-1]の領域を確保する
		void Resize(ll size) { N = size; data.resize(size); }
		/**
		* @brief 半開区間[l, r)の合計を取得する
		* @note
		* l < r になるように指定すること
		* 範囲外の区間を指定したときは範囲内に調整して合計を返す
		**/
		T Sum(ll l, ll r)
		{
			if (l < 0) l = 0;
			if (N < l || r < 0) return 0;
			if (N < r) r = N;
			assert(l <= r);
			return sum(r) - sum(l);
		}
	private:
		ll N;
		std::vector<T> data;
		T sum(ll r)
		{
			T s = 0;
			while (r > 0) s += data[r - 1], r -= r & -r;
			return s;
		}
	};
}

実装例
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5655897