An affine range update replaces every reading x in [l,r) with a*x+b under a fixed modulus. A segment-tree node stores its interval sum and one pending affine transformation for children that have not yet been visited. Applying a new transformation to a node of length k changes its sum to a*sum+b*k. If the node already carries an older pending transformation x maps to m*x+c, then the new pending pair becomes a*m and a*c+b; reversing that composition gives wrong results when updates overlap. Before a partial update or query descends, the pending transform is pushed to both children and reset to the identity pair (1,0). This model requires a nonempty fixed array, supports negative multipliers by reduction modulo the configured modulus, and uses half-open ranges. It does not expose min, max, or assignment as separate operations, although assignment can be represented by multiplier zero.
Affine lazy segment trees: compose range calibration before summing
Operational case
Start with readings [47,19,61,29,83] modulo 1009. Applying x maps to 3x+7 over positions [1,4) gives a total sum of 478, of which the transformed middle interval contributes 348. Applying x maps to 2x+5 over [2,5) next raises the total to 860, and the final three positions sum to 749. The second update overlaps two earlier corrected readings, so its pending transformation must be composed after the first. An empty range has sum zero and an empty update makes no change. The modulus is part of the stored arithmetic contract; changing it after construction would invalidate every cached sum and pending pair.
Working Python program
class AffineReadingTree:
def __init__(self, readings, modulus=1009):
if not readings or modulus < 2:
raise ValueError("need readings and a modulus of at least two")
self.size = len(readings)
self.modulus = modulus
capacity = 4 * self.size
self.sums = [0] * capacity
self.pending_multiply = [1] * capacity
self.pending_add = [0] * capacity
def build(node, left, right):
if right - left == 1:
self.sums[node] = readings[left] % modulus
return
middle = (left + right) // 2
build(node * 2, left, middle)
build(node * 2 + 1, middle, right)
self.sums[node] = (self.sums[node * 2] + self.sums[node * 2 + 1]) % modulus
build(1, 0, self.size)
def _apply(self, node, length, multiply, add):
modulus = self.modulus
self.sums[node] = (multiply * self.sums[node] + add * length) % modulus
self.pending_multiply[node] = multiply * self.pending_multiply[node] % modulus
self.pending_add[node] = (multiply * self.pending_add[node] + add) % modulus
def _push(self, node, left, right):
if right - left == 1:
return
multiply, add = self.pending_multiply[node], self.pending_add[node]
if multiply == 1 and add == 0:
return
middle = (left + right) // 2
self._apply(node * 2, middle - left, multiply, add)
self._apply(node * 2 + 1, right - middle, multiply, add)
self.pending_multiply[node], self.pending_add[node] = 1, 0
def transform(self, start, stop, multiply, add):
if not 0 <= start <= stop <= self.size:
raise IndexError("range must be half-open and within readings")
multiply %= self.modulus
add %= self.modulus
def visit(node, left, right):
if stop <= left or right <= start:
return
if start <= left and right <= stop:
self._apply(node, right - left, multiply, add)
return
self._push(node, left, right)
middle = (left + right) // 2
visit(node * 2, left, middle)
visit(node * 2 + 1, middle, right)
self.sums[node] = (self.sums[node * 2] + self.sums[node * 2 + 1]) % self.modulus
visit(1, 0, self.size)
def range_sum(self, start, stop):
if not 0 <= start <= stop <= self.size:
raise IndexError("range must be half-open and within readings")
def visit(node, left, right):
if stop <= left or right <= start:
return 0
if start <= left and right <= stop:
return self.sums[node]
self._push(node, left, right)
middle = (left + right) // 2
return (visit(node * 2, left, middle) + visit(node * 2 + 1, middle, right)) % self.modulus
return visit(1, 0, self.size)
if __name__ == "__main__":
index = AffineReadingTree([47, 19, 61, 29, 83])
index.transform(1, 4, 3, 7)
print(index.range_sum(0, 5), index.range_sum(1, 4))
index.transform(2, 5, 2, 5)
print(index.range_sum(0, 5), index.range_sum(2, 5))Output
478 348
860 749Time, space, and tradeoff
A full-cover update changes one node in O(1), while a partial range visits O(log N) boundary paths and a bounded number of covered nodes, so each update and range-sum query costs O(log N) time. The tree and two pending arrays use O(N) space, and recursion uses O(log N) call depth. Values are always reduced modulo the configured modulus; this does not preserve an unreduced physical reading. A plain prefix-sum array answers static sums faster but cannot repair overlapping calibration ranges without rebuilding later prefixes. An ordinary range-add lazy tree needs only one pending offset; affine updates need both multiplier and addend in the right composition order.
Common Mistakes
- Do not reverse the order of old and new affine transformations.
- Do not forget the addend times interval length in a node sum.
- Do not descend with a stale pending transform on the parent.
- Do not compare a modular sum with an unreduced real-world total.
Connected lessons
- Range Queries
- Data Structures
- Lazy segment tree: add to a range and query its minimum
- Segment trees: combine child ranges after updates
- Segment tree beats: cap a range while retaining its sum
- Two-dimensional segment trees: correct sensors and sum rectangles
- Disjoint sparse tables: immutable sums with constant-time queries
- Two-stack window aggregation: keep FIFO order under a monoid
- Projects
- Quizzes
Compare this operation boundary with Persistent range MEX: search last occurrences in prefix versions, Range XOR bases: merge linear spans in a segment tree, Min-max heaps: remove either end of one dispatch priority array, then complete the audit project and decision quiz.
Maximum-subarray segment trees: preserve the crossing burst examines a related structure with a different operation boundary.