Abstract / Summary

Design a data structure that supports adding numbers to an array and quickly getting the sum of any range.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 43% (800k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Indexed Tree
• Design
• Divide And Conquer
• Segment Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The class implements a mutable integer array that supports point updates and range-sum queries. It partitions the underlying data into fixed-size buckets and maintains a running total for each bucket. By combining direct element access for the edges of a query with pre-computed bucket totals for the interior, the implementation achieves fast query performance while keeping updates inexpensive.

Initialization

When an instance is created, the constructor stores the original list in self.data. It also creates a dictionary self.partial that maps a bucket index to the sum of all elements that belong to that bucket. The bucket size is fixed at 100, so the bucket index for element i is computed as i // self.bucketsize. The loop iterates over every element, adds the element to the appropriate bucket total, and therefore builds the auxiliary structure in a single linear pass.

self.data = nums
self.partial = defaultdict(int)
self.bucketsize = 100
for i in range(len(nums)):
    bucket = i // self.bucketsize
    self.partial[bucket] += nums[i]

Update Operation

The update method replaces the value at a given index with a new value. It first computes the difference between the new value and the current value, stores the new value back into self.data, and then adjusts the pre-computed bucket sum by the same difference. Because only one bucket is affected, the update runs in constant time.

diff = val - self.data[index]
self.data[index] = val
bucket = index // self.bucketsize
self.partial[bucket] += diff

Range-Sum Query

The sumRange method returns the sum of elements between left and right inclusive. It handles three distinct phases:

1. Small-range shortcut - If the interval length is less than twice the bucket size, the method falls back to a simple loop over the elements. This avoids the overhead of bucket arithmetic for short ranges.

    if right - left < 2*self.bucketsize:
        for i in range(left, right + 1):
            result += self.data[i]
        return result

2. Alignment to bucket boundaries - The method advances left until it lands on the start of a bucket, adding each stepped-over element directly to the result. This guarantees that the subsequent bucket-wise loop starts at a clean bucket boundary.

    while left % self.bucketsize != 0:
        result += self.data[left]
        left += 1

3. Fast bucket accumulation - With left now aligned, the method computes the bucket indices for the left and right ends. It then iterates over all full buckets that lie completely inside the query interval, adding the pre-computed bucket sums from self.partial. After processing these interior buckets, any remaining elements in the final partial bucket are summed individually.

    bucketLeft  = left // self.bucketsize
    bucketRight = right // self.bucketsize
   
    for b in range(bucketLeft, bucketRight):
        result += self.partial[b]
        left   += self.bucketsize
   
    while left <= right:
        result += self.data[left]
        left   += 1

The method finally returns the accumulated result.

Edge Cases Handled

The implementation gracefully deals with queries that start or end exactly on a bucket boundary. The alignment loop stops immediately when left is already aligned, so no extra work is performed. When right falls inside the same bucket as left after alignment, the bucket loop is skipped because bucketLeft equals bucketRight, and the trailing while-loop processes the remaining elements correctly. The small-range shortcut also covers the situation where the entire interval fits within a single bucket, ensuring that the algorithm never attempts to read beyond the array bounds.

If the query range consists of a single element (left == right), the small-range condition is satisfied and the method returns that element directly. The update logic similarly works for the first or last element of a bucket because the bucket index calculation uses integer division, which maps any valid index to the correct bucket.

Performance Optimizations

The core optimization is the use of fixed-size buckets with pre-computed sums. By storing a sum per bucket, the algorithm reduces the number of element-wise additions required for large intervals. The bucket size of 100 strikes a balance: it keeps the number of buckets modest, limiting the memory overhead of self.partial, while still providing a noticeable reduction in per-query work compared to a naïve linear scan.

The early-exit for small ranges avoids the overhead of bucket calculations when they would not provide a benefit. This conditional path ensures that short queries run in pure O(k) time where k is the length of the interval, without the constant-time cost of bucket alignment and loop setup.

Updates are performed in constant time because only a single bucket total needs to be adjusted. The use of a defaultdict(int) for self.partial eliminates the need for explicit existence checks when updating bucket sums, further streamlining the update path.

Overall, the combination of bucketed aggregation, boundary alignment, and a short-range shortcut yields an implementation that scales well for both frequent updates and frequent large range queries.

Imagine a very long row of numbered toy boxes. Each box has a single number written on it. To keep things organized, these boxes are grouped together into sets of one hundred boxes. Every group has a special sticker on the outside that tells the total sum of all the numbers inside those one hundred boxes.

When someone asks to find the sum of all the numbers between two spots in the row, the code looks at how far apart those spots are. If the spots are close together, the code just walks down the line, looks at each individual box, and adds up the numbers one by one.

If the spots are far apart, the code does something clever to be faster. It looks at the individual boxes at the very beginning until it reaches the edge of a group. Then, instead of counting every single box one by one, it looks at the special sticker on the outside of each full group and adds the whole total at once. This saves a lot of time because it does not have to check every single box. Once it reaches the last few boxes at the end, it counts those individually just like at the start.

If a number inside one of the boxes ever changes, the code first updates that specific number in the main list. Then, it figures out which group that box belongs to and updates the special sticker to match the new sum. This way, the information is always ready to go for the next time someone asks for a sum.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java					TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			Go	C#	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei				Rust
	black-shadows	C++
	charles-wangkai			Java
	everthis					JS
	fengvyi	C++
	Garvit244		Python
	halfrost						Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	qiyuangong		Python
	ruoru				Rust
	suxrobGM							C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality