Leetcode.com problem 307: "Range Sum Query"

James S. Plank

Thu Aug 4 03:21:40 PM EDT 2022

Problem Statement.
Success Rate (as of August, 2022): 40.5%
Medium Problem
example-1.txt - An example input for testing.
main.cpp - A main with a bunch of testing functionality.
tests.sh - A shell script to test your answer.
answers.txt - What the output of tests.sh should be.

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:

You set the sum to sleft, which ish 22.
You go to the node's parent -- the one whose val is -54.
Since we are the node's left child, we do nothing.
You go -54's parent, which is the root.
Since we are the node's right child, we add the parent's sleft value to the sum: 22 + 73 = 95. There's our answer.

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!

Testing

To test yourself, my main.cpp implements the following commands:

NEW a b c d ..: This calls the constructor on the given values.
UPDATE index val: This calls update()
SUMRANGE left right: This calls sumRange() and prints the answer.
NEWRAND seed num: This creates a random vector with num integers. The seed is used to seed the RNG.
URAND seed num: This makes num random update calls.
SUMRAND seed num: This makes num sumRange() calls and prints their sum.
SUMRAND-P seed num: This makes num sumRange() calls but prints left and right for each call.
PRINTV: This prints the last vector used.

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.