Find the min of indices 1 to 6. Start at the root. A node fully inside the range gives its answer and stops. One fully outside is skipped. One that straddles the edge is split into its children.
The code
Segment Tree, in Python
def query(node, lo, hi, l, r):
if r < lo or hi < l: return IDENTITY
if l <= lo and hi <= r: return tree[node]
mid = (lo + hi) // 2
return combine(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r))
def update(node, lo, hi, i, v):
if lo == hi: tree[node] = v; return
mid = (lo + hi) // 2
if i <= mid: update(2 * node, lo, mid, i, v)
else: update(2 * node + 1, mid + 1, hi, i, v)
tree[node] = combine(tree[2 * node], tree[2 * node + 1])
def range_add(node, lo, hi, l, r, v):
if r < lo or hi < l: return # outside: nothing to do
if l <= lo and hi <= r: # fully inside: apply here, tag the rest
tree[node] += v * (hi - lo + 1); lazy[node] += v; return # the children are not touched
push(node, lo, hi) # a pending tag goes down before we look below
mid = (lo + hi) // 2
range_add(2 * node, lo, mid, l, r, v); range_add(2 * node + 1, mid + 1, hi, l, r, v)
tree[node] = tree[2 * node] + tree[2 * node + 1]
def push(node, lo, hi): # hand the tag to both children
if lazy[node] == 0 or lo == hi: return
mid = (lo + hi) // 2
tree[2 * node] += lazy[node] * (mid - lo + 1); lazy[2 * node] += lazy[node]
tree[2 * node + 1] += lazy[node] * (hi - mid); lazy[2 * node + 1] += lazy[node]
lazy[node] = 0
Segment Tree, in JavaScript
function query(node, lo, hi, l, r) {
if (r < lo || hi < l) return IDENTITY;
if (l <= lo && hi <= r) return tree[node];
const mid = Math.floor((lo + hi) / 2);
return combine(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r));
}
function update(node, lo, hi, i, v) {
if (lo === hi) { tree[node] = v; return; }
const mid = Math.floor((lo + hi) / 2);
if (i <= mid) update(2 * node, lo, mid, i, v); else update(2 * node + 1, mid + 1, hi, i, v);
tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
}
function rangeAdd(node, lo, hi, l, r, v) {
if (r < lo || hi < l) return; // outside: nothing to do
if (l <= lo && hi <= r) { // fully inside: apply here, tag the rest
tree[node] += v * (hi - lo + 1); lazy[node] += v; return; // the children are not touched
}
push(node, lo, hi); // a pending tag goes down before we look below
const mid = Math.floor((lo + hi) / 2);
rangeAdd(2 * node, lo, mid, l, r, v); rangeAdd(2 * node + 1, mid + 1, hi, l, r, v);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
function push(node, lo, hi) { // hand the tag to both children
if (lazy[node] === 0 || lo === hi) return;
const mid = Math.floor((lo + hi) / 2);
tree[2 * node] += lazy[node] * (mid - lo + 1); lazy[2 * node] += lazy[node];
tree[2 * node + 1] += lazy[node] * (hi - mid); lazy[2 * node + 1] += lazy[node];
lazy[node] = 0;
}
Segment Tree, in Kotlin
fun query(node: Int, lo: Int, hi: Int, l: Int, r: Int): Int {
if (r < lo || hi < l) return IDENTITY
if (l <= lo && hi <= r) return tree[node]
val mid = (lo + hi) / 2
return combine(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r))
}
fun update(node: Int, lo: Int, hi: Int, i: Int, v: Int) {
if (lo == hi) { tree[node] = v; return }
val mid = (lo + hi) / 2
if (i <= mid) update(2 * node, lo, mid, i, v) else update(2 * node + 1, mid + 1, hi, i, v)
tree[node] = combine(tree[2 * node], tree[2 * node + 1])
}
fun rangeAdd(node: Int, lo: Int, hi: Int, l: Int, r: Int, v: Int) {
if (r < lo || hi < l) return // outside: nothing to do
if (l <= lo && hi <= r) { // fully inside: apply here, tag the rest
tree[node] += v * (hi - lo + 1); lazy[node] += v; return // the children are not touched
}
push(node, lo, hi) // a pending tag goes down before we look below
val mid = (lo + hi) / 2
rangeAdd(2 * node, lo, mid, l, r, v); rangeAdd(2 * node + 1, mid + 1, hi, l, r, v)
tree[node] = tree[2 * node] + tree[2 * node + 1]
}
fun push(node: Int, lo: Int, hi: Int) { // hand the tag to both children
if (lazy[node] == 0 || lo == hi) return
val mid = (lo + hi) / 2
tree[2 * node] += lazy[node] * (mid - lo + 1); lazy[2 * node] += lazy[node]
tree[2 * node + 1] += lazy[node] * (hi - mid); lazy[2 * node + 1] += lazy[node]
lazy[node] = 0
}