セグメント木

目的

長さnの数列valに対して、加算val[k]+=vと区間最小値の計算$\min_{l \le i\lt r}val[i]$の二つのクエリを$O(\log n)$で行うデータ構造。

計算量

$O(N\log N)$

使い方

int n
数列valの長さ
long[] val
数列val
void setVal(int k,long v)
val[k]にvを代入
void addVal(int k,long v)
val[k]にvを加算
long query(int a,int b)
$\min_{a \le i\lt b}val[i]$をreturn

ソースコード

class SegTree {
	int n;
	long[] val;
	
	public SegTree(int n_) {
		n = 1;
		while (n < n_)
			n *= 2;
		val = new long[2 * n - 1];
		Arrays.fill(val, Long.MAX_VALUE / 3);
	}

	void setVal(int k, long v) {
		k += n - 1;
		val[k] = Math.min(val[k], v);
		while (k > 0) {
			k = (k - 1) / 2;
			val[k] = Math.min(val[2 * k + 1], val[2 * k + 2]);
		}
	}

	void addVal(int k, long v) {
		k += n - 1;
		val[k] += v;
		while (k > 0) {
			k = (k - 1) / 2;
			val[k] = Math.min(val[2 * k + 1], val[2 * k + 2]);
		}
	}

	long query(int a, int b, int l, int r, int k) {
		if (a <= l && r <= b) {
			return val[k];
		} else  if (r <= a || b <= l) {
			return Long.MAX_VALUE / 3;
		} else  {
			return Math.min(query(a, b, l, (l + r) / 2, 2 * k + 1), query(a, b, (l + r) / 2, r, 2 * k + 2));
		}
	}
		long query(int a, int b) {
		return query(a, b, 0, n, 0);
	}
}