NyaaLIB::DS_FenwickTree

Fenwick Tree (Binary Indexed Tree)
点加算クエリと区間合計取得クエリを で処理する

メンバ関数

• operator[i]: 要素[i]の値を取得
• resize(size): sizeにリサイズする
• add(i, x): 要素[i]に値xを加算
• sum(l, r): 半開区間[l, r)の合計を取得

関数詳細

• T sum(ll l, ll r)

半開区間[l, r)の合計を取得
になるように指定すること
範囲外の区間を指定したときは範囲内に調整して合計を返す

#include <bits/stdc++.h>

namespace NyaaLIB
{
#ifndef _DS_FENWICK_TREE_
#define _DS_FENWICK_TREE_

	template <class T = long long> struct DS_FenwickTree
	{
		using ll = long long;
		DS_FenwickTree() {}
		DS_FenwickTree(ll n) : n(n), data(n) {}
		T operator [](ll i) { return sum(i, i + 1); }
		void resize(ll size) { n = size; data.resize(size); }
		void add(ll i, T x)
		{
			assert(0 <= i && i < n);
			i++; while (i <= n) data[i - 1] += x, i += i & -i;
		}
		T sum(ll l, ll r)
		{
			if (l < 0) l = 0;
			if (n < r) r = n;
			if (n < l || r < 0 || l == r) return 0;
			assert(l < r);
			return sum(r) - sum(l);
		}
	private:
		ll n = 0;
		std::vector<T> data;
		T sum(ll r)
		{
			T s = 0;
			while (r > 0) s += data[r - 1], r -= r & -r;
			return s;
		}
	};

#endif
}

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