Add 3 to every value in indices 2 to 6. Updating each leaf and every ancestor would cost O(n). Instead, descend from the root: a node fully inside the range takes the whole addition at once, 3 times the leaves under it, and keeps a tag saying its children still owe 3 each. The children are not visited. Tags only move when something later needs to look below them.
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
}