Square-root blocks: update one capacity and sum a range

Operational case

A depot has seven daily capacities: 23, 47, 19, 61, 38, 52, and 29. The window [1, 6) totals 217. Correct the value at position three from 61 to 74; that same window now totals 230. The correction raises one cached block by 13. Query [4, 4) and receive zero without reading any capacity. These outputs are useful acceptance checks because the main window crosses block boundaries, the corrected position lies inside it, and the empty window tests the half-open convention. An invalid index is rejected before the block total changes.

Working Python program

from math import isqrt


class BlockCapacitySums:
    def __init__(self, capacities):
        self.values = list(capacities)
        self.block_size = max(1, isqrt(len(self.values)))
        self.blocks = [0] * ((len(self.values) + self.block_size - 1) // self.block_size)
        for position, capacity in enumerate(self.values):
            self.blocks[position // self.block_size] += capacity

    def replace(self, position, capacity):
        if not 0 <= position < len(self.values):
            raise IndexError("capacity position outside batch")
        self.blocks[position // self.block_size] += capacity - self.values[position]
        self.values[position] = capacity

    def sum_between(self, start, stop):
        if not 0 <= start <= stop <= len(self.values):
            raise IndexError("invalid half-open capacity range")
        total = 0
        while start < stop:
            if start % self.block_size == 0 and start + self.block_size <= stop:
                total += self.blocks[start // self.block_size]
                start += self.block_size
            else:
                total += self.values[start]
                start += 1
        return total


if __name__ == "__main__":
    ledger = BlockCapacitySums([23, 47, 19, 61, 38, 52, 29])
    print("before=", ledger.sum_between(1, 6), sep="")
    ledger.replace(3, 74)
    print("after=", ledger.sum_between(1, 6), sep="")
    print("empty=", ledger.sum_between(4, 4), sep="")

Output

before=217
after=230
empty=0

Time, space, and tradeoff

For N values and a block width near the square root of N, construction scans O(N) values and retains O(N) values plus O(sqrt N) block sums. Replacement costs O(1). A query touches at most two partial blocks and O(sqrt N) full blocks, so its worst-case time is O(sqrt N). For very small arrays, a plain scan may be faster and simpler. Compared with a Fenwick tree, this design offers a cheaper point replacement but a slower range query. It does not offer range assignment, minimum queries, array insertion, or automatic resizing; changing array length requires rebuilding the block partition.

Common Mistakes

• Do not count a partial block both element by element and by its cached sum.
• Do not forget to apply the replacement difference to the cached block.
• Do not treat the stop index as included.
• Do not claim logarithmic query time for this fixed-width block scan.

Connected lessons

• Range Queries
• Data Structures
• Fenwick trees: update points and query prefix totals
• Segment trees: combine child ranges after updates
• Prefix sums: trade one scan for constant-time ranges
• Projects
• Quizzes

Compare its contract with Merge-sort trees: count readings below a threshold in one interval, Disjoint sparse tables: immutable sums with constant-time queries, Li Chao trees: minimum linear tariff at a chosen quantity, then apply the range workload project and check the range-index quiz.

Mo ordering: count distinct scan codes across an offline query batch extends this operation choice.

Range-mode indexes: combine complete-block modes with fringe candidates adds a related structure with a different operation boundary.