VvyLw's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub

:warning: Java/library/ds/fenwicktree/RangeBIT.java

Depends on

Required by

Code

package library.ds.fenwicktree;

import java.util.stream.IntStream;

/**
 * Range Add Range Sum
 * 区間加算, 区間和
 */
public final class RangeBIT {
	private final int n;
	private final FenwickTree a, b;
	/**
	 * コンストラクタ
	 * @param n サイズ
	 */
	public RangeBIT(final int n) {
		this.n = n;
		a = new FenwickTree(n + 1);
		b = new FenwickTree(n + 1);
	}
	/**
	 * コンストラクタ
	 * @param arr
	 */
	public RangeBIT(final int[] arr) {
		this(arr.length);
		for(int i = 0; i < arr.length; ++i) {
			add(i, i, arr[i]);
		}
	}
	/**
	 * コンストラクタ
	 * @param arr
	 */
	public RangeBIT(final long[] arr) {
		this(arr.length);
		for(int i = 0; i < arr.length; ++i) {
			add(i, i, arr[i]);
		}
	}
	/**
	 * 半開区間[l, r)に要素を加算
	 * @param l
	 * @param r
	 * @param x
	 */
	public final void add(final int l, final int r, final long x) {
		a.add(l, x);
		a.add(r, -x);
		b.add(l, x * (1 - l));
		b.add(r, x * (r - 1));
	}
	/**
	 * RangeBIT[i]を返す
	 * @param i
	 * @return i番目の要素
	 */
	public final long get(final int i){ return sum(i, i + 1); }
	/**
	 * 半開区間[l, r)の和を返す
	 * @param l
	 * @param r
	 * @return 半開区間[l, r)の和
	 */
	public final long sum(int l, int r) {
		l--;
		r--;
		return a.sum(r) * r + b.sum(r) - a.sum(l) * l - b.sum(l);
	}
	/**
	 * RangeBITを配列に変換したものを返す
	 * @return RangeBITの配列
	 */
	public final long[] toArray(){ return IntStream.range(0, n).mapToLong(this::get).toArray(); }
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		sb.append(get(0));
		for(int i = 0; ++i < n;) {
			sb.append(", " + get(i));
		}
		return "[" + sb.toString() + "]";
	}
}
Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/user_defined.py", line 68, in bundle
    raise RuntimeError('bundler is not specified: {}'.format(str(path)))
RuntimeError: bundler is not specified: Java/library/ds/fenwicktree/RangeBIT.java
Back to top page