Leetcode.com problem 307: "Range Sum Query"

James S. Plank

Thu Aug 4 03:21:40 PM EDT 2022

This was the first Leetcode problem I did where I had to implement a class. I really didn't know how they were going to test, even though they say it in the writeup. So I simply put a vector of ints into the class and implemented the operations in the straightforward way -- having sumRange() be O(nums.size()).

That didn't work.

It was too slow because they'll test it on a vector with 30,000 elements, and they'll make 30,000 calls to sumRange(), which results in 900,000,000 operations. That was the point at which I understood how they were doing the testing.

So we need to do something smarter. What I did was turn nums into a balanced binary tree. I defined a Node struct, and then put the following recursive method into my class:

Node *create(int low, int high, Node *parent, const vector <int> &vals);

This returned the node that is the root of the tree of the given range of vals (those are indices -- you call create(0, vals.size()-1, NULL, vals) as your initial call.

Besides having a pointer to the root, I kept a vector of the nodes, so that I could access a node directory by its integer when I needed to implement sumRange().

Each of my nodes contained an integer sleft, which is the sum of the node's value and all of the elements in its left subtree. Here's an example. Suppose vals is:

8 2 0 4 59 22 -54 89 5

Then, here's my tree:

How does this help implement sumRange(). Well, given the index of a node, you can calculate the sum of all the vals from 0 to that index in (log n) time. For example, suppose I want to find the sum of all the vals from index 0 to index 5. You can see from the array, that the answer is 95. How do you calculate that in O(log n) time from the tree? Start with the node whose index is 5 (it's val is 22). Set your sum to its sleft value. Now chase parent pointers to the root. If you are your parent's right child, then you add the parent's sleft to the sum.

Let's do this example, where we start with the node whose val is 22:

So, to implement sumRange(), you calculate these values for left and right and use subtraction (you'll need to add the left value after that).

What about update()? Well, you'll have to adjust values of sleft up to the root. I'll let you figure it out.

My solution didn't beat any records, but it was fast enough!


To test yourself, my main.cpp implements the following commands: You'll note that the RAND calls let you test large numbers of calls without a lot of printing -- that helps you time your program. My tests.sh ran in under a second.