VvyLw's Library

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

View the Project on GitHub

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

Depends on

Required by

Code

package library.ds.fenwicktree;

import java.util.stream.IntStream;

/**
 * FenwickTree(Binary Indexed Tree[BIT])
 * @see <a href="https://nyaannyaan.github.io/library/data-structure/binary-indexed-tree.hpp">参考元</a>
 */
public final class FenwickTree {
	private final int n;
	private final long[] data;
	/**
	 * コンストラクタ
	 * @param sz サイズ
	 */
	public FenwickTree(final int sz) {
		n = sz + 2;
		data = new long[n + 1];
	}
	/**
	 * コンストラクタ
	 * @param a int型の配列
	 */
	public FenwickTree(final int[] a) {
		this(a.length);
		IntStream.range(0, a.length).forEach(i -> add(i, a[i]));
	}
	/**
	 * コンストラクタ
	 * @param a long型の配列
	 */
	public FenwickTree(final long[] a) {
		this(a.length);
		IntStream.range(0, a.length).forEach(i -> add(i, a[i]));
	}
	/**
	 * 閉区間[0, k]の和を返す
	 * @param k
	 * @return 閉区間[0, k]の和
	 */
	public final long sum(int k) {
		if(k < 0) {
			return 0;
		}
		long ret = 0;
		for(++k; k > 0; k -= k & -k) {
			ret += data[k];
		}
		return ret;
	}
	/**
	 * 閉区間[l, r]の和
	 * @param l
	 * @param r
	 * @return 閉区間[l, r]の和
	 */
	public final long sum(final int l, final int r){ return sum(r) - sum(l - 1); }
	/**
	 * FenwickTree[k]を返す
	 * @param k
	 * @return k番目の要素
	 */
	public final long get(final int k){ return sum(k) - sum(k - 1); }
	/**
	 * k番目に値を加算
	 * @param k
	 * @param x
	 */
	public final void add(int k, final long x) {
		for(++k; k < n; k += k & -k) {
			data[k] += x;
		}
	}
	/**
	 * 閉区間[l, r]に値を加算する
	 * @param l
	 * @param r
	 * @param x
	 */
	public final void add(final int l, final int r, final long x) {
		add(l, x);
		add(r + 1, -x);
	}
	private final int lg(final int n){ return 31 - Integer.numberOfLeadingZeros(n); }
	/**
	 * 閉区間[0, k]の区間和がw以上となるような最小のk
	 * @apiNote 要素は全て非負
	 * @param w
	 * @return [0, k]の区間和がw以上となるような最小のk
	 */
	public final int lowerBound(long w) {
		if(w <= 0) {
			return 0;
		}
		int x = 0;
		for(int k = 1 << lg(n); k > 0; k >>= 1) {
			if(x + k <= n - 1 && data[x + k] < w) {
				w -= data[x + k];
				x += k;
			}
		}
		return x;
	}
	/**
	 * 閉区間[0, k]の区間和がwよりも大きくなるような最小のk
	 * @apiNote 要素は全て非負
	 * @param w
	 * @return [0, k]の区間和がwよりも大きくなるような最小のk
	 */
	public final int upperBound(long w) {
		if(w < 0) {
			return 0;
		}
		int x = 0;
		for(int k = 1 << lg(n); k > 0; k >>= 1) {
			if(x + k <= n - 1 && data[x + k] <= w) {
				w -= data[x + k];
				x += k;
			}
		}
		return x;
	}
	/**
	 * FenwickTreeの累積和を返す
	 * @return FenwickTreeの累積和
	 */
	public final long[] toArray(){ return IntStream.rangeClosed(0, n).mapToLong(this::sum).toArray(); }
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		sb.append(sum(0));
		for(int i = 0; ++i < n - 2;) {
			sb.append(", " + sum(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/FenwickTree.java
Back to top page