Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
SegmentTreePractice
/**
* 練習問題1
*
* - i 番目の値を v に変更する。(update)
* - l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、インデックスの合計を出力。(min)
*/
public class SegmentTreePractice1 {
int N;
int M;
// 区間が持つ値
static class NodeValue {
// 最小値
int min;
// インデックスの和
long minIndexSum;
public NodeValue(int m, long i) {
min = m;
minIndexSum = i;
}
public NodeValue clone() {
return new NodeValue(min, minIndexSum);
}
public static NodeValue zero() {
return new NodeValue(Integer.MAX_VALUE, 0);
}
}
NodeValue[] values;
public SegmentTreePractice1(int[] data) {
// 実装の都合上、最下段のノード数を2の乗数にする
N = Integer.highestOneBit(data.length-1)<<2;
// M : 最下段の左端のインデックス
M = (N >> 1) - 1;
values = new NodeValue[N];
for (int i = 0 ; i < data.length ; i++) {
// 最下段を初期化
values[M+i] = new NodeValue(data[i], i);
}
for (int i = M+data.length ; i < N ; i++) {
// 余白をゼロ値で埋める
values[i] = NodeValue.zero();
}
for (int i = M-1 ; i >= 0 ; i--) {
// 初期化のため、上の段についてマージ処理を呼ぶ。
// i*2+1 : i番目の左の子
// i*2+2 : i番目の右の子
values[i] = merge(values[i*2+1], values[i*2+2]);
}
}
/**
* マージ処理
*/
public NodeValue merge(NodeValue left, NodeValue right) {
if (left.min == right.min) {
return new NodeValue(left.min, left.minIndexSum + right.minIndexSum);
} else if (left.min < right.min) {
return left.clone();
} else {
return right.clone();
}
}
/**
* クエリ1: idx番目の値をvalueに更新。
*/
public void update(int idx, int value) {
values[M+idx].min = value;
int i = M+idx;
while (true) {
// 親に移動
i = (i-1) >> 1;
// 親の更新をするため、マージ処理を呼ぶ
values[i] = merge(values[i*2+1], values[i*2+2]);
// 一番上まで到達したら抜ける
if (i == 0) {
break;
}
}
}
/**
* クエリ2: [l,r)の最小値と、そのインデックスの和を求める。
*/
public NodeValue min(int l, int r) {
return min(l, r, 0, 0, M+1);
}
private NodeValue min(int l, int r, int idx, int fr, int to) {
if (to <= l || r <= fr) {
// クエリの指定区間外ならゼロ値を返す
return NodeValue.zero();
}
if (l <= fr && to <= r) {
// 今の区間がクエリの指定区間にすっぽり入ってたら、その区間の値を返す
return values[idx].clone();
}
// med: 現在の区間の中間。最初に呼ぶ M+1 は 2の乗数になってるので、必ず割り切れる
int med = (fr+to) / 2;
// 左の区間について答えを求める
NodeValue left = min(l, r, idx*2+1, fr, med);
// 右の区間について答えを求める
NodeValue right = min(l, r, idx*2+2, med, to);
// 左右の結果をマージする
return merge(left, right);
}
}
import java.util.Arrays;
/**
* 練習問題2
*
* - i 番目の値を v に変更する。(update)
* - l 番目から r 番目の値の中で、最も左端で v 以下になるインデックスを求める。(findIndexLessThanV)
*/
public class SegmentTreePractice2 {
int N;
int M;
int[] seg;
public SegmentTreePractice2(int[] data) {
N = Integer.highestOneBit(data.length-1)<<2;
M = (N >> 1) - 1;
seg = new int[N];
Arrays.fill(seg, Integer.MAX_VALUE);
for (int i = 0 ; i < data.length ; i++) {
seg[M+i] = data[i];
}
for (int i = M-1 ; i >= 0 ; i--) {
seg[i] = compute(i);
}
}
/**
* Uodates value at position minIndexSum.
*
* @param idx
* @param value
*/
public void update(int idx, int value) {
seg[M+idx] = value;
int i = M+idx;
while (true) {
i = (i-1) >> 1;
seg[i] = compute(i);
if (i == 0) {
break;
}
}
}
private int compute(int i) {
return Math.min(seg[i*2+1], seg[i*2+2]);
}
public int findIndexLessThanV(int l, int r, int v) {
int ret = findIndexLessThanV(l, r, 0, 0, M+1, v);
if (ret == Integer.MAX_VALUE) {
return -1;
}
return ret;
}
private int findIndexLessThanV(int l, int r, int idx, int fr, int to, int v) {
// 区間外
if (to <= l || r <= fr) {
return Integer.MAX_VALUE;
}
// vよりでかい
if (seg[idx] > v) {
return Integer.MAX_VALUE;
}
// ここ以下、必ず答えが存在
int med = (fr+to) / 2;
if (l <= fr && to <= r) {
int len = to-fr;
if (len == 1) {
// 最下段
return idx-M;
}
}
int left = findIndexLessThanV(l, r, idx*2+1, fr, med, v);
if (left < Integer.MAX_VALUE) {
// 左の答えがINFでないなら左を優先して返す
return left;
} else {
// 左に無いなら、右に必ず答えがある
return findIndexLessThanV(l, r, idx*2+2, med, to, v);
}
}
}
/**
* 練習問題3
*
* - l 番目から r 番目の値を v に変更する。(update)
* - l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、最も左端のインデックスを求めること。(min)
*/
public class SegmentTreePractice3 {
static final int INF = 1000000010;
int N;
int M;
// 区間が持つ値
static class NodeValue {
// 最小値
int min;
// 最左インデックス
int minIndex;
// 遅延評価中の最小値
int delayMin;
// 遅延評価中の最左インデックス
int delayMinIndex;
public NodeValue(int m, int idx) {
min = m;
minIndex = idx;
delayMin = INF;
delayMinIndex = INF;
}
public NodeValue clone() {
return new NodeValue(min, minIndex);
}
public static NodeValue zero() {
return new NodeValue(Integer.MAX_VALUE, 0);
}
}
NodeValue[] values;
public SegmentTreePractice3(int[] data) {
// 実装の都合上、最下段のノード数を2の乗数にする
N = Integer.highestOneBit(data.length-1)<<2;
// M : 最下段の左端のインデックス
M = (N >> 1) - 1;
values = new NodeValue[N];
for (int i = 0 ; i < data.length ; i++) {
// 最下段を初期化
values[M+i] = new NodeValue(data[i], i);
}
for (int i = M+data.length ; i < N ; i++) {
// 余白をゼロ値で埋める
values[i] = NodeValue.zero();
}
for (int i = M-1 ; i >= 0 ; i--) {
// 初期化のため、上の段についてマージ処理を呼ぶ。
// i*2+1 : i番目の左の子
// i*2+2 : i番目の右の子
values[i] = merge(values[i*2+1], values[i*2+2]);
}
}
/**
* マージ処理
*/
public NodeValue merge(NodeValue left, NodeValue right) {
if (left.min <= right.min) {
return left.clone();
} else {
return right.clone();
}
}
/**
* 遅延評価中の値があれば適用しつつ子供に下ろす
*/
public void pushDown(int idx, int fr, int to) {
if (values[idx].delayMin == INF) {
// 遅延評価してないし
return;
}
// 自分に適用
values[idx].min = values[idx].delayMin;
values[idx].minIndex = values[idx].delayMinIndex;
if (idx >= M) {
// 最下段には子がいないので終了
return;
}
// 左右の子に下ろす
int left = idx*2+1;
int right = idx*2+2;
// 左の子の最左位置は fr
values[left].delayMin = values[idx].delayMin;
values[left].delayMinIndex = fr;
// 右の子の最左位置は fr と to の中間
values[right].delayMin = values[idx].delayMin;
values[right].delayMinIndex = (fr + to) / 2;
// 遅延評価してない状態にリセット
values[idx].delayMin = INF;
values[idx].delayMinIndex = INF;
}
/**
* 左右の子のデータを吸い上げて適用する。
*/
public void pullUp(int idx) {
NodeValue newValue = merge(values[idx*2+1], values[idx*2+2]);
values[idx].min = newValue.min;
values[idx].minIndex = newValue.minIndex;
}
/**
* クエリ1: [l,r)の値を v に更新する。
*/
public void update(int l, int r, int v) {
update(l, r, v, 0, 0, M+1);
}
public void update(int l, int r, int v, int idx, int fr, int to) {
// 遅延評価中の値を持っていた場合、子供に下ろす
pushDown(idx, fr, to);
if (to <= l || r <= fr) {
return;
}
if (l <= fr && to <= r) {
// 遅延評価中の値を積む
values[idx].delayMin = v;
values[idx].delayMinIndex = fr;
// 子に下ろす
pushDown(idx, fr, to);
return;
}
// 左右の子を更新
int med = (fr + to) / 2;
update(l, r, v, idx*2+1, fr, med);
update(l, r, v, idx*2+2, med, to);
// 左右の子の現在の値が `min`, `minIndex` に入ってるため、吸い上げる
pullUp(idx);
}
/**
* クエリ2: [l,r)の最小値と、そのインデックスの和を求める。
*/
public NodeValue min(int l, int r) {
return min(l, r, 0, 0, M+1);
}
private NodeValue min(int l, int r, int idx, int fr, int to) {
// 遅延評価中の値を持っていた場合、子供に下ろす
pushDown(idx, fr, to);
if (to <= l || r <= fr) {
// クエリの指定区間外ならゼロ値を返す
return NodeValue.zero();
}
if (l <= fr && to <= r) {
// 今の区間がクエリの指定区間にすっぽり入ってたら、その区間の値を返す
return values[idx].clone();
}
// med: 現在の区間の中間。最初に呼ぶ M+1 は 2の乗数になってるので、必ず割り切れる
int med = (fr+to) / 2;
// 左の区間について答えを求める
NodeValue left = min(l, r, idx*2+1, fr, med);
// 右の区間について答えを求める
NodeValue right = min(l, r, idx*2+2, med, to);
// 左右の子の現在の値が `min`, `minIndex` に入ってるため、吸い上げる
pullUp(idx);
// 左右の結果をマージする
return merge(left, right);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment