Segment trees for minimum and sum queries
Use one segment-tree design for sums, minima and ordered concatenation by requiring an associative combine operation and the right neutral element.

A segment tree stores aggregates for intervals and combines a small set of those intervals to answer a query. The same structure can support sums or minima if its combine operation is associative and has a neutral element. For a developer implementing range queries with updates, those algebraic conditions explain both the reusable design and several common bugs.
For sums, combine with addition and use zero as the neutral element. For minima over finite numbers, combine with min and use positive infinity. Combining any valid value with the neutral element must leave the value unchanged. The empty interval then has a defined result, and unused padding leaves cannot change a real query. The Python example assumes familiarity with loops and zero-based list indices; it does not require an earlier tree implementation.
Store a complete tree over padded leaves
Round the leaf count up to a power of two. Store the original values at consecutive leaves and fill remaining leaves with the neutral element. Each internal node combines its left child’s aggregate with its right child’s aggregate. Building from the bottom visits every internal node once.
class SegmentTree:
def __init__(self, values, combine, identity):
values = list(values)
self.n = len(values)
self.combine, self.identity = combine, identity
self.size = 1
while self.size < self.n:
self.size *= 2
self.tree = [identity] * (2 * self.size)
self.tree[self.size:self.size + self.n] = values
for i in range(self.size - 1, 0, -1):
self.tree[i] = combine(self.tree[2 * i], self.tree[2 * i + 1])
def set(self, position, value):
if type(position) is not int or not 0 <= position < self.n:
raise IndexError(position)
i = self.size + position
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.combine(self.tree[2 * i], self.tree[2 * i + 1])
def query(self, left, right):
if (type(left) is not int or type(right) is not int
or not 0 <= left <= right <= self.n):
raise IndexError('invalid half-open range')
left += self.size
right += self.size
before = after = self.identity
while left < right:
if left & 1:
before = self.combine(before, self.tree[left])
left += 1
if right & 1:
right -= 1
after = self.combine(self.tree[right], after)
left //= 2
right //= 2
return self.combine(before, after)
values = [5, 2, 7, 1, 3]
sums = SegmentTree(values, lambda a, b: a + b, 0)
mins = SegmentTree(values, min, float('inf'))
assert sums.query(1, 4) == 10
assert mins.query(1, 4) == 1
sums.set(3, 6)
mins.set(3, 6)
assert sums.query(1, 4) == 15
assert mins.query(1, 4) == 2
The constructor captures a finite iterable once, allowing a generator without asking for its length first. This extra list stores O(n) references. Index arguments must be built-in integers; booleans and fractional positions are rejected. The input and query positions are zero based, and the right endpoint is exclusive. The padded leaf positions are an internal detail. The bounds check prevents a caller from querying beyond the original data even though additional neutral leaves exist.
For the original query [1, 4), the tree can combine [1, 2) with [2, 4). Their sum aggregates are two and eight, giving ten. Their minimum aggregates are two and one, giving one. The decomposition is the same; only the combine operation changes.
Associativity permits regrouping, not reordering
An associative operation satisfies combine(combine(a, b), c) = combine(a, combine(b, c)). A query can therefore group consecutive values according to tree nodes without changing the result. Commutativity, which would permit swapping a and b, is not required.
String concatenation is an example: regrouping preserves a string, but reversing two segments does not. The query keeps separate left and right accumulators for that reason. Segments discovered on the left append to before; segments discovered on the right prepend to after. Combining them at the end restores the original interval order.
letters = SegmentTree(iter('abcdefgh'), lambda a, b: a + b, '')
assert letters.query(1, 7) == 'bcdefg'
assert letters.query(2, 2) == ''
For [1, 7), the right side first discovers g and later ef. Prepending produces efg; appending incorrectly produces gef. The left accumulator contains bcd, so the incorrect final answer would be bcdgef. A query such as [1, 4) does not exercise this two-block right boundary and would miss the defect. Sum and minimum tests also miss it because their operations are commutative. The AtCoder segment-tree documentation states the associative-operation and identity requirements explicitly.
Updates revisit one ancestor path
Changing one leaf affects only the intervals containing that position. Recompute the parent, then its parent, until reaching the root. The height is O(log n), so a point assignment has that cost. A range query selects at most a constant number of boundary nodes at each level and also costs O(log n).
These bounds count combine calls and assume each combine and aggregate copy costs O(1). The padded size is less than twice a positive input length, so the tree has O(n) aggregate slots and construction makes O(n) combine calls. Empty input is represented with neutral storage; only its empty range is valid. The returned identity for an empty minimum query is a convention indicating no finite member, not an actual observed minimum.
The CP-Algorithms segment-tree guide explains interval decomposition and common extensions. Range updates require additional machinery such as lazy propagation. Calling set for every position in a long update interval does not inherit the logarithmic cost of one point assignment.
Choose an aggregate with the right semantics
Floating-point addition is not exactly associative, so a tree’s grouping can produce a different rounded sum from a left-to-right scan. That is a numerical limitation of the operation, not an indexing error. If reproducible financial totals are required, a fixed decimal or integer-unit representation may be more appropriate under the application’s rules.
The implementation also assumes combining values does not mutate shared identity objects or child aggregates. A mutable list used as the identity with an in-place append operation would violate that expectation because several storage positions initially reference the same object. Use immutable aggregates or construct independent objects with a carefully defined combine function.
Test all short intervals after each point update and compare with direct aggregation. Include an empty range, a final-position update, and a length that is not a power of two. Run at least one noncommutative aggregate such as concatenation to verify interval order. The algebraic contract lets the code be generic; the tests should verify that contract rather than only one convenient numeric operation.
Compose transformations without copying strings
Concatenation is a useful order test, but its copying cost means it is not a constant-time aggregate. With one character per leaf, each level can hold O(n) characters across its strings, giving O(n log n) character storage. Returning a long string also takes time proportional to its length. The tree’s logarithmic number of combine calls does not erase that work.
A compact ordered aggregate is an affine function f(x) = a*x + b, stored as the pair (a, b). Interpret an interval from left to right: apply its first transformation, then its second. Combining (a, b) with (c, d) therefore gives (c*a, c*b + d). Function composition is associative; it usually is not commutative. The identity is (1, 0).
def then(first, second):
a, b = first
c, d = second
return c * a, c * b + d
transforms = [(2, 0), (1, 3), (-1, 0), (1, 4)]
functions = SegmentTree(iter(transforms), then, (1, 0))
assert functions.query(1, 4) == (-1, 1)
a, b = functions.query(1, 4)
assert a * 5 + b == -4
assert functions.query(0, 0) == (1, 0)
functions.set(2, (1, 0))
assert functions.query(1, 4) == (1, 7)
The original interval adds three, negates the result, then adds four. Starting from five gives eight, minus eight, then minus four. Reversing the order instead gives minus six, so a correct unordered set of operations is insufficient. After replacing negation with the identity, the interval simply adds seven. This example tests both composition order and a point assignment using immutable two-number aggregates.
Python integer coefficients can grow as transformations compose, so arithmetic bit cost still matters even with a fixed number of fields. AtCoder explicitly qualifies its complexity by the cost of its operation. Also require a pure combine function that is defined for every reachable aggregate: this small implementation does not roll back a point assignment if user-supplied combine code raises halfway through rebuilding ancestors.
As an exercise, replace the final “add four” with “double”, derive the interval’s coefficients by hand, and compare all nonempty intervals with direct application to several integers. Then deliberately change the right accumulator to append and find the shortest failing interval in the eight-letter fixture. The two tests isolate algebraic direction from numeric coincidence.