NyaaLIB::DS_NyaaImos

いもす法　区間加算 、区間総和取得 、更新処理
https://imoz.jp/algorithms/imos_method.html
累積和の機能を追加することで累積和の上位互換としても使える。
単純な累積和だと値の更新はできないが、このライブラリは任意のタイミングで値の更新も可能。

#include <bits/stdc++.h>

namespace NyaaLIB
{
	/**
	* いもす法ライブラリ
	* 区間加算O(1)、区間総和取得O(1)、更新処理O(N)
	**/

	template <class T = long long> struct DS_NyaaImos
	{
		using ll = long long;
		ll sz;
		std::vector<T> add;
		std::vector<T> sum;
		std::vector<T> val;

		// 半開区間[0,size)、つまり閉区間[0,size-1]のメモリを確保する
		DS_NyaaImos(ll size) : sz(size) { add.resize(sz), sum.resize(sz), val.resize(sz); }
		DS_NyaaImos(std::vector<T>& v) : sz(ll(v.size()))
		{	// 配列を入力としたときはメモリ確保と同時に累積和も作成する
			add.resize(sz), sum.resize(sz), val = v, sum[0] = v[0];
			for (ll i = 1; i < sz; i++) sum[i] += sum[i - 1] + val[i];
		}

		void Add(ll i, T x)
		{	// 配列[i]に値xを加算する（範囲外なら何もしない）
			if (i < 0 || sz <= i) return;
			add[i] += x;
			if (i == sz - 1) return;
			add[i + 1] -= x;
		}

		/**
		* @note
		* 半開区間[l, r)に対して値xだけ加算する
		* [l,r)が範囲外のときは範囲内に丸めて処理する
		**/
		void Add(ll l, ll r, T x)
		{
			if (l < 0) l = 0;
			add[l] += x;
			if (sz <= r) return;
			add[r] -= x;
		}

		ll Range(ll l, ll r)
		{	// 半開区間[l,r)の合計値を返す（lやrが範囲外のときは0を返す）
			if (l < 0) l = 0;
			if (sz < r) r = sz;
			if (r <= 0 || sz <= l) return 0;
			return (l == 0) ? sum[r - 1] : sum[r - 1] - sum[l - 1];
		}

		decltype(val)& Update(void)
		{	// 結果を返すと同時に累積和の更新もする
			for (ll i = 1; i < sz; i++) add[i] += add[i - 1];
			for (ll i = 0; i < sz; i++) val[i] += add[i];
			sum[0] = val[0];
			for (ll i = 1; i < sz; i++) sum[i] = sum[i - 1] + val[i];
			fill(all(add), 0);
			return val;
		}

		// 配列[i]の値を返す
		ll Val(ll i) { return val[i]; }
	};
}

実装例
https://atcoder.jp/contests/abc037/submissions/24426859
https://atcoder.jp/contests/abc014/submissions/24426874