Skip to content

Instantly share code, notes, and snippets.

@mrchnk

mrchnk/segment-tree.js

Last active April 23, 2021 06:34
Show Gist options
  • Save mrchnk/69492c7b6967e7a8ef89efd12216ab2d to your computer and use it in GitHub Desktop.
Save mrchnk/69492c7b6967e7a8ef89efd12216ab2d to your computer and use it in GitHub Desktop.
Download ZIP
Raw
segment-tree.js
function SegmentTree(size, merge, zero) {
const tree = [];
return {
tree,
update(index, value) {
update(0, 0, size - 1, index, value)
},
query(l, r) {
return query(0, 0, size - 1, l, r)
},
build(values) {
build(0, 0, size - 1, values);
}
};
function query(v, tl, tr, l, r) {
if (l === tl && r === tr) {
return tree[v] || zero;
}
const tm = Math.floor((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 {
const lq = query(v * 2 + 1, tl, tm, l, tm);
const rq = query(v * 2 + 2, tm + 1, tr, tm + 1, r);
return merge(lq, rq);
}
}
function update(v, tl, tr, index, value) {
if (tl === tr) {
return tree[v] = value;
} else {
const tm = Math.floor((tl + tr) / 2);
let vl, vr;
if (index <= tm) {
vl = update(v * 2 + 1, tl, tm, index, value);
vr = tree[v * 2 + 2] || zero;
} else {
vl = tree[v * 2 + 1] || zero;
vr = update(v * 2 + 2, tm + 1, tr, index, value);
}
return tree[v] = merge(vl, vr);
}
}
function build(v, tl, tr, values) {
if (tl === tr) {
return tree[v] = values[tl];
} else {
const tm = Math.floor((tl + tr) / 2);
const vl = build(v * 2 + 1, tl, tm, values);
const vr = build(v * 2 + 2, tm + 1, tr, values);
return tree[v] = merge(vl, vr);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment