A prefix-sum array answers an interval sum quickly because its input is fixed. If values change between queries, the old prefixes describe the old array. Rebuilding all of them after every change is correct, but can take linear time for each update. We need a representation in which one change leaves most of the stored information useful.
Partitioning the array into moderately sized blocks gives one such representation. A query scans entries near its two endpoints and uses one stored total for each complete block between them. A range addition follows the same partition: change individual entries at the ends, and record a deferred addition for a complete block. The deferred addition is useful only if its meaning stays precise when a later operation touches part of that block.
We will support operations in their given order, without sorting queries or assuming that all updates happen first. This is a different use of square-root ideas from Mo's algorithm, whose static input and reversible moving interval have their own invariants.
Separate the logical array from its representation
Let be an integer array with . A range is half-open: contains indices , where . In particular, is allowed and describes an empty range. An addition with integer increment changes each entry in the range to ; a query returns their sum, with empty sum zero.
Choose a block size . Block has start , end , and actual length . There are nonempty blocks. The last block can be shorter than .
Definition 1.5.1
(The base, deferred addition and true total invariant)
Store one base value per index and two quantities per block: a deferred addition and a total . Their meanings are
Thus is the sum of the logical entries, not merely the sum of the stored base entries. Initially copy the input into , set every to zero, and sum the input within each block to obtain .
The base array is an implementation device. After a whole-block addition, reading alone need not return the current value.
Derive the two update rules
If an addition covers a whole block, leave its bases unchanged and set
Every logical entry increases by , and the total increases once for each of the block's entries. This is constant work, regardless of the block's length.
If an addition covers only a subset of a block, keep unchanged, add to each with , and increase by . Updating the affected bases already changes the required logical entries, since their common deferred addition remains the same. We do not need to distribute the old deferred addition to every base before doing this.
Proposition 1.5.2
(The lazy block invariant is preserved)
Start from the initialized structure and apply every addition by the two rules above: a complete block changes and , and a partial block changes the selected bases and . Then after any finite sequence of additions, for all , and for every block.
Proof
(Each rule changes exactly one term)
Before the update, the selected entry is . Replacing by makes it . Unselected bases and the deferred addition are unchanged, so all other logical entries are unchanged.
The sum of the bases rises by and the term is unchanged. Increasing by exactly therefore restores both equalities in the invariant. The whole-block rule satisfies the same equalities by changing the second term instead. Initialization and these two cases prove the invariant after every finite sequence of additions. ∎
Proof X-ray
What the lazy-block proof depends on
The non-obvious move is that the invariant is stated about the sum , not about either term alone. A partial update never has to distribute to the bases: it changes one summand and the other stays valid. A whole-block update changes the other summand. Each rule is correct because it alters exactly one of the two terms, which is also why applying both would count twice.
The hypothesis that carries the weight is additivity: shifting every entry of a block by shifts its sum by , where is the actual length of the block. That fact lets be updated in constant time. It fails for a minimum or a maximum, which move by rather than . The proof is an induction over the sequence of operations, and it uses nothing about the block size or the sign of .
For a sum query, a complete block contributes . For a partially covered block, read each selected logical entry as . These contributions must form a disjoint partition of ; otherwise a correct block total can still be counted twice.
Concept lensAlgebraic
Additions and queries as vector operations
Let be the indicator vector of the range. The logical array is , an addition adds to , and a query is the dot product . The indicator splits as a sum of complete-block indicators plus at most single-entry indicators. The first part is handled by the block scalars and , the second entry by entry.
A trace with two deferred blocks
Worked example 1.5.3
(A complete block and a short last block both receive lazy additions)
Take , , and
The blocks are , and , initially with totals and deferred additions . Add to . The first block changes only at indices 2 and 3. The other two blocks are fully covered, including the last block of length two.
| Block | Stored bases after the addition | Deferred addition | True total |
|---|---|---|---|
The logical array is now . Query by taking logical entry 3, the whole middle block, and logical entry 8. Its sum is .
Next add to . The middle bases become , its deferred addition remains , and its total falls from to . Its logical entries are . Repeating query now gives .
Counterexample mode
A deferred addition must be neither forgotten nor applied twice
Suppose a block has bases , deferred addition , and total . Its logical entries are . Adding only to the first entry should give . Change the bases to , keep the deferred addition , and change the total to .
If we instead reset the deferred addition to zero without first adding it to every base, the represented values become . If we handle a whole-block addition by increasing both every base and the deferred addition, each logical entry receives the increment twice. Each update rule should change exactly one of the two terms in .
Partition a range without endpoint special cases
Start at . Let be the block containing and compute its true end . If and , the entire block lies in the remaining range. Process that block and advance to . Otherwise process only index and advance it by one.
Proposition 1.5.4
(The partition loop consumes exactly the requested range)
For , the loop started at processes disjoint pieces, each a single index or a complete block, whose union is , and it stops with .
Proof
(The processed prefix)
At the start of an iteration, the indices already processed are exactly , and none outside that interval has been processed. The full-block branch consumes , which is inside because and . The single-entry branch consumes , also inside the request because the loop requires .
Both branches append a nonempty interval immediately after the processed prefix. They neither overlap earlier work nor skip an index. Each strictly increases , and neither takes it past . Termination at gives a disjoint complete partition. An empty range enters no iteration; therefore needs no block lookup. ∎
Worked example 1.5.5
(Both endpoints in one block, and an empty range)
Start again from with and add to . At the block is and , so only index is processed; likewise index . Both bases change, to and , the deferred addition stays , and the block total rises by , from to . The query then takes the whole block and returns , which equals . The query uses the three block totals , and and returns . The empty query enters no iteration, so it returns without any block lookup.
There are at most two partially covered blocks: the block containing the left endpoint and the block containing the last included index. All blocks strictly between them are complete. If both endpoints lie in one block, that block is scanned just once. The loop's full-block test also recognizes a complete short final block; testing i + B <= r would fail to recognize it.
Executable implementation
This implementation assumes integer input values, increments and indices. It rejects an empty input array and invalid bounds; it accepts empty operation ranges. The constructor copies the input, so operations do not mutate the caller's list.
from math import isqrt
class SqrtRangeAddSum:
def __init__(self, values):
self.base = list(values)
self.n = len(self.base)
if self.n == 0:
raise ValueError("the array must be nonempty")
self.size = isqrt(self.n - 1) + 1
count = (self.n + self.size - 1) // self.size
self.lazy = [0] * count
self.total = [0] * count
for i, value in enumerate(self.base):
self.total[i // self.size] += value
def _bounds(self, left, right):
if not 0 <= left <= right <= self.n:
raise ValueError("invalid half-open range")
def add(self, left, right, delta):
self._bounds(left, right)
i = left
while i < right:
block = i // self.size
end = min(self.n, (block + 1) * self.size)
if i == block * self.size and end <= right:
self.lazy[block] += delta
self.total[block] += (end - i) * delta
i = end
else:
self.base[i] += delta
self.total[block] += delta
i += 1
def sum(self, left, right):
self._bounds(left, right)
answer = 0
i = left
while i < right:
block = i // self.size
end = min(self.n, (block + 1) * self.size)
if i == block * self.size and end <= right:
answer += self.total[block]
i = end
else:
answer += self.base[i] + self.lazy[block]
i += 1
return answer
def assign(self, index, value):
if not 0 <= index < self.n:
raise IndexError("invalid array index")
block = index // self.size
delta = value - (self.base[index] + self.lazy[block])
self.base[index] += delta
self.total[block] += delta
The formula isqrt(n - 1) + 1 equals for positive integer , including perfect squares. The code does not use a floating-point square root. Arithmetic is exact for Python integers; the operation counts below count integer arithmetic steps rather than bit operations on unbounded values.
For assignment, let be the requested value. The old logical value is , so the required increment is . Applying the partial-update rule to this one entry makes it exactly . Setting the base to directly would instead represent .
Worked example 1.5.6
(Assignment after a partial update keeps the existing lazy state)
Continue the ten-entry example after both additions. Index 6 has base and deferred addition , so its current logical value is . Assign it the value . The change is . Its base becomes , while the block's deferred addition remains and total falls from to .
The middle block now represents , whose sum is indeed . Query therefore returns . Other entries, including those sharing the same deferred addition, retain their values.
Why the square root appears
Proposition 1.5.7
(Cost of range additions and sums)
For block size , a range addition or a range sum takes time in the worst case, hence for . Initialization takes time and a point assignment takes time.
Proof
(Boundary entries and complete blocks)
For a general block size , a range operation processes at most two partial blocks, each containing at most individually processed entries, and at most complete blocks. Each iteration does constant work in the arithmetic model. Consequently both a range addition and a range sum take
worst-case time. Initialization takes time; the bases and block arrays use cells. A point assignment takes time with this representation. For the code's , the number of blocks is at most , so each range operation is . ∎
This bound describes arbitrary interleavings and does not rely on an amortized average. It also does not say every request costs a square root: a complete block is processed in one iteration, while an empty range takes constant time. Very small or very large blocks give cheap work of one kind and expensive work of the other kind.
Counterexample mode
A true sum needs the actual block length
For and , the last block has two entries. Adding to that complete block increases its sum by , not . Using the nominal size in the total update would produce an incorrect full-block answer even though reading its individual logical entries still gives the correct values. Maintaining entry values alone does not establish the total invariant.
Common mistake
(Reading a base entry as the current value)
After adding to in the trace, the base is still , but the logical value is . The base array is a representation detail. Whenever a deferred addition is nonzero, reading alone gives the wrong value; add the block's deferred addition.
Common mistake
(Counting blocks by floor division)
For and the blocks start at , so there are of them and the last holds one entry. Computing the count as allocates too few block records, and index falls in a block that does not exist. Use the ceiling .
The method relies on the algebra of addition and sums: a uniform increment changes a block's sum by its length times . Other aggregates or updates need their own invariants. For example, a whole-block minimum changes by , rather than by ; its partial updates also cannot use the sum rule. An arbitrary replacement of a block by one value needs a different deferred-operation design.
Exercises with complete solutions
Quick check
(1. In the ten-entry example, after adding 3 to [2,10), why is the middle block total 16 even though its stored bases sum to 4? Compute .)
Solution · 1. Include the deferred contribution exactly once
The middle block has length four, base sum , and deferred addition . Its true total is . The two boundary entries have logical values and , so the requested sum is . Adding the deferred contribution again to the stored total would double-count it.
Quick check
(2. A block has bases [2,3], deferred addition 4 and total 13. Add -5 only to its first entry. Give all new stored quantities and both logical values.)
Solution · 2. A negative partial addition preserves the lazy tag
The new bases are , the deferred addition remains , and the total becomes . The logical entries are , whose sum is . The unchanged second base and common deferred addition preserve the second entry.
Quick check
(3. The short last block has bases [5,3], deferred addition zero and total 8. Add 3 to the entire block. Why is a new stored total of 20 wrong?)
Solution · 3. Count represented entries, not nominal capacity
There are two entries, so the deferred addition becomes and the total becomes . The logical entries are . The value comes from using four as the block length: . That counts two positions outside the array and breaks the total equality.
Quick check
(4. A programmer handles a partial update by changing the selected bases and resetting the block's deferred addition to zero. Use bases [1,2] and deferred addition 5 to show the failure. What extra work would make resetting valid?)
Solution · 4. Clearing a deferred addition requires materializing it everywhere
Adding only to the first logical entry should change to . Updating the first base to and clearing the deferred addition instead represents . To clear it validly, first add to every base, producing , then set the deferred addition to zero and perform the partial change, giving bases and total . That approach is correct but scans the whole block; preserving the deferred addition avoids that extra work.
Quick check
(5. Why do both B=1 and B=n permit linear-time range operations in the worst case? Does a constant-time full-array query when B=n contradict the bound?)
Solution · 5. Whole blocks and boundary scans must both be counted
For , querying the whole array processes complete singleton blocks. For , there is one block, but a range such as scans entries when . Thus neither extreme guarantees sublinear worst-case range operations as grows. A full-array query for uses the one stored total and is constant time; a worst-case upper bound need not be attained by every request.
Quick check
(6. After the example's two additions, index 6 has base zero, deferred addition 3 and block total 12. Assign logical value -4. Compute the required base, new block total and .)
Solution · 6. Assignment is a difference from the logical old value
The old value is , so the increment is . The base becomes , the deferred addition remains , and the block total becomes . The queried boundary entries remain and , so the answer is . Writing base directly would represent , not the requested .