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:
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!