Skip to content

Instantly share code, notes, and snippets.

@mrchnk

mrchnk/SegmentTree.java

Created May 21, 2021 19:35
Show Gist options
  • Save mrchnk/6d197ec0910b4ae35654dd156eb9b86c to your computer and use it in GitHub Desktop.
Save mrchnk/6d197ec0910b4ae35654dd156eb9b86c to your computer and use it in GitHub Desktop.
Download ZIP
Raw
SegmentTree.java
private static class SegmentTree {
private final long[] tree;
private final int size;
public SegmentTree(int size) {
this.tree = new long[size * 4];
this.size = size;
}
protected long merge(long l, long r) {
return l + r;
}
public void build(long[] values) {
build(0, 0, size - 1, values);
}
private long build(int v, int tl, int tr, long[] values) {
if (tl == tr) {
return tree[v] = values[tl];
} else {
var tm = (tl + tr) / 2;
var vl = build(v * 2 + 1, tl, tm, values);
var vr = build(v * 2 + 2, tm + 1, tr, values);
return tree[v] = merge(vl, vr);
}
}
public void update(int index, long value) {
update(0, 0, size - 1, index, value);
}
private long update(int v, int tl, int tr, int index, long value) {
if (tl == tr) {
return tree[v] = value;
} else {
var tm = (tl + tr) / 2;
long vl, vr;
if (index <= tm) {
vl = update(v * 2 + 1, tl, tm, index, value);
vr = tree[v * 2 + 2];
} else {
vl = tree[v * 2 + 1];
vr = update(v * 2 + 2, tm + 1, tr, index, value);
}
return tree[v] = merge(vl, vr);
}
}
public long query(int l, int r) {
return query(0, 0, size - 1, l, r);
}
private long query(int v, int tl, int tr, int l, int r) {
if (l == tl && r == tr) {
return tree[v];
} else {
var tm = (tl + tr) / 2;
if (r <= tm) {
return query(v * 2 + 1, tl, tm, l, r);
} else if (l >= tm + 1) {
return query(v * 2 + 2, tm + 1, tr, l, r);
} else {
var lq = query(v * 2 + 1, tl, tm, l, tm);
var rq = query(v * 2 + 2, tm + 1, tr, tm + 1, r);
return merge(lq, rq);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment