Segmented arrays: locate blocks through cumulative lengths

A segmented array stores an ordered sequence in small array blocks and keeps an aligned list of cumulative end offsets. Binary search over those offsets finds the block containing a numeric index; subtracting the preceding end gives the offset inside it. This version appends to the last block, splits an overflowing block, removes empty blocks, and merges adjacent blocks when they fit. Every cumulative end must equal the number of items through its block, and ends must strictly increase because no stored block is empty. Unlike an unrolled linked list, the outer block array permits binary search for an indexed read. Middle edits change later cumulative counts and can shift entries in the outer Python lists. That maintenance cost is explicit rather than hidden under a claimed logarithmic update.

Operational case

The incident IDs alert-47, alert-19, alert-61, and alert-83 are split into blocks of at most three. Inserting alert-29 at position two and removing alert-19 changes the same logical sequence as the unrolled-list example. The cumulative ends identify which block owns the third item, alert-61, without following links from the head. If an edit alters a block near the front, all later end offsets must be repaired before the next binary search. Failing to update just one count can return a plausible but wrong incident from a neighboring block.

Working Python program

from bisect import bisect_right


class SegmentedIncidentArray:
    def __init__(self, block_capacity=4):
        if block_capacity < 2:
            raise ValueError("block capacity must be at least two")
        self.capacity = block_capacity
        self.blocks = []
        self.ends = []

    def __len__(self):
        return self.ends[-1] if self.ends else 0

    def _position(self, index):
        block_index = bisect_right(self.ends, index)
        previous_end = self.ends[block_index - 1] if block_index else 0
        return block_index, index - previous_end

    def _refresh_from(self, block_index):
        running = self.ends[block_index - 1] if block_index else 0
        for offset in range(block_index, len(self.blocks)):
            running += len(self.blocks[offset])
            self.ends[offset] = running

    def append(self, incident_id):
        if not self.blocks or len(self.blocks[-1]) == self.capacity:
            self.blocks.append([])
            self.ends.append(len(self))
        self.blocks[-1].append(incident_id)
        self.ends[-1] += 1

    def at(self, index):
        if not 0 <= index < len(self):
            raise IndexError("index outside incident array")
        block_index, offset = self._position(index)
        return self.blocks[block_index][offset]

    def insert(self, index, incident_id):
        if not 0 <= index <= len(self):
            raise IndexError("insert outside incident array")
        if index == len(self):
            self.append(incident_id)
            return
        block_index, offset = self._position(index)
        block = self.blocks[block_index]
        block.insert(offset, incident_id)
        if len(block) > self.capacity:
            middle = len(block) // 2
            self.blocks.insert(block_index + 1, block[middle:])
            self.ends.insert(block_index + 1, 0)
            del block[middle:]
        self._refresh_from(block_index)

    def delete(self, index):
        if not 0 <= index < len(self):
            raise IndexError("delete outside incident array")
        block_index, offset = self._position(index)
        block = self.blocks[block_index]
        removed = block.pop(offset)
        if not block:
            self.blocks.pop(block_index)
            self.ends.pop(block_index)
        elif block_index + 1 < len(self.blocks) and len(block) + len(self.blocks[block_index + 1]) <= self.capacity:
            block.extend(self.blocks.pop(block_index + 1))
            self.ends.pop(block_index + 1)
        self._refresh_from(block_index)
        return removed

    def values(self):
        return [incident for block in self.blocks for incident in block]


events = SegmentedIncidentArray(block_capacity=3)
for incident in ("alert-47", "alert-19", "alert-61", "alert-83"):
    events.append(incident)
events.insert(2, "alert-29")
events.delete(1)
print("order=", events.values(), " third=", events.at(2), sep="")

Output

order=['alert-47', 'alert-29', 'alert-61', 'alert-83'] third=alert-61

Time, space, and tradeoff

For B blocks of maximum capacity C, at(index) costs O(log B) to binary-search cumulative ends and O(1) to access a block item. A middle insert or deletion costs O(B + C): local shifts and splits cost O(C), and later prefix counts or outer block-list positions can cost O(B). Appending at the tail is amortized O(1) in this Python-list model, including occasional new-block allocation; worst-case list growth can copy outer storage. Traversal and values() cost O(N). Space is O(N + B). The faster indexed read does not imply faster middle edits than an unrolled list or a plain array for small N.

Common Mistakes

Do not binary-search stale cumulative ends after an edit.
Do not retain an empty block with a duplicate end offset.
Do not describe middle edits as logarithmic because lookup uses binary search.
Do not confuse a block reference count with packed memory bytes.

Connected lessons

Compare its edit and lookup costs with Gap buffers: pay when the edit cursor crosses text, Ropes: share text chunks across immutable revisions, Unrolled lists: link small blocks instead of single items, then run the sequence audit and contract quiz.

Gap labels: compare dispatch order across middle inserts adds a related structure with a different operation boundary.