Skip to content

Instantly share code, notes, and snippets.

@brpapa
Last active December 30, 2019 05:32
Show Gist options
  • Save brpapa/0cbbcc3b08b53fc1fe6f62b47f62fa68 to your computer and use it in GitHub Desktop.
Save brpapa/0cbbcc3b08b53fc1fe6f62b47f62fa68 to your computer and use it in GitHub Desktop.
segment tree
// [ql .. qr]: intervalo de consulta
int rangeQuery(int v, int l, int r, int ql, int qr) {
// v: índice atual da bt
// [l .. r]: intervalo atual de arr
if (ql > r || qr < l)
// [l .. r] está completamente fora de [ql .. qr]
return INF;
if (l >= ql && r <= ql)
// [l .. r] está completamente dentro de [ql .. qr]
return bt[v]; // rmq(l, r)
// [l .. r] contém [ql .. qr]
int mid = (l + r) / 2;
return min(
rangeQuery(2*v+1, l, mid, ql, qr),
rangeQuery(2*v+2, mid+1, r, ql, qr)
);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment