library/TemplateDynamicSegmentTree.java

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

Depends on

• library/FastIO.java

Verified with

• library/TemplateDynamicSegmentTree_small_test.java
• library/TemplateDynamicSegmentTree_test.java

Code

package library;

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

class TemplateDynamicSegmentTree<T> {
	class NodeST {
		T val;
		NodeST l = null;
		NodeST r = null;
		NodeST() { val = eSupplier.get(); }
		NodeST(T val) { this.val = val; }
	}

	long n;
	Supplier<T> eSupplier;
	T e;
	BinaryOperator<T> f;

	NodeST root;

	// O(1)
	TemplateDynamicSegmentTree(long len, Supplier<T> eSupplier, BinaryOperator<T> f) {
		FastIO.nonNegativeCheck(len);
		this.n = len; this.eSupplier = eSupplier; this.e = eSupplier.get(); this.f = f;
		root = new NodeST();
	}

	// O(logN)
	void set(long i, T val) { FastIO.rangeCheck(i, n); update(i, val, false); }
	void update(long i, T val) { FastIO.rangeCheck(i, n); update(i, val, true); }
	void update(long i, T val, boolean update) { update(root, 0, n, i, val, update); }
	NodeST update(NodeST t, long l, long r, long i, T val, boolean update) {
		if(t == null) t = new NodeST();
		if(r - l == 1) { t.val = update ? f.apply(t.val, val) : val; return t; }
		long mid = (l + r) >> 1;
		if(i < mid) t.l = update(t.l, l, mid, i, val, update);
		else t.r = update(t.r, mid, r, i, val, update);
		t.val = eSupplier.get();
		if(t.l != null) t.val = f.apply(t.val, t.l.val);
		if(t.r != null) t.val = f.apply(t.val, t.r.val);
		return t;
	}

	// O(logN)
	T get(long i) { FastIO.rangeCheck(i, n); return get(root, 0, n, i); }
	T get(NodeST t, long l, long r, long i) {
		if(t == null) return e;
		if(r - l == 1) return t.val;
		long mid = (l + r) >> 1;
		return i < mid ? get(t.l, l, mid, i) : get(t.r, mid, r, i);
	}
	T find(long l0, long r0) {
		FastIO.inclusiveRangeCheck(l0, n);
		FastIO.inclusiveRangeCheck(r0, n);
		FastIO.assertion(l0 <= r0, "l is larger than r.");
		return find(root, 0, n, l0, r0);
	}
	T find(NodeST t, long l, long r, long l0, long r0) {
		if(l == r || t == null || r0 <= l || r <= l0) return e;
		if(l0 <= l && r <= r0) return t.val;
		long mid = (l + r) >> 1;
		return f.apply(find(t.l, l, mid, l0, r0), find(t.r, mid, r, l0, r0));
	}
}

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