library/SparseTable.java

• View this file on GitHub
• Last update: 2023-03-23 19:06:36+09:00

Depends on

• library/FastIO.java

Verified with

• library/SparseTable_test.java

Code

package library;

import java.util.function.*;
import library.FastIO;

class SparseTable {
	LongBinaryOperator f;

	int n;
	int m;
	long table[][];

	SparseTable(long[] a, LongBinaryOperator f) { // O(NlogN)
		this.f = f;
		n = a.length;
		m = 1;
		while(1 << m < n) m ++;
		table = new long[m][n];
		for(int i = 0; i < n; i ++) table[0][i] = a[i];
		for(int i = 1; 1 << i < n; i ++) {
			for(int j = 1 << i; j < n + (1 << i); j += 1 << i + 1) {
				for(int k = 0; k < 1 << i && j + k < n; k ++) {
					table[i][j + k] = k == 0 ? a[j + k] : f.applyAsLong(table[i][j + k - 1], a[j + k]);
				}
				int k0 = Math.max(1, j - n + 1);
				for(int k = k0; k <= 1 << i; k ++) {
					table[i][j - k] = k == k0 ? a[j - k] : f.applyAsLong(a[j - k], table[i][j - k + 1]);
				}
			}
		}
	}

	long get(int i) { FastIO.rangeCheck(i, n); return table[0][i]; } // O(1)

	long find(int l, int r) { // O(1)
		r --;
		FastIO.rangeCheck(l, n);
		FastIO.rangeCheck(r, n);
		FastIO.assertion(l <= r, "l is larger than r.");
		int log = Long.numberOfTrailingZeros(Integer.highestOneBit(l ^ r));
		return l == r ? get(l) : f.applyAsLong(table[log][l], table[log][r]);
	}
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/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 "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/user_defined.py", line 71, in bundle
    return subprocess.check_output(shlex.split(command))
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/subprocess.py", line 466, in check_output
    return run(*popenargs, stdout=PIPE, timeout=timeout, check=True,
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/subprocess.py", line 571, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['false']' returned non-zero exit status 1.

Back to top page