Working with ranges: Fenwick trees

Let’s talk about Fenwick trees(a.k.a. Binary Indexed Trees) for a moment and see how we can use them to solve range problems. This is not a tutorial, just a few notes for my future self. By the way, I already posted about this topic some time ago, this time, however, I’ll focus my attention on a particular kind of problem. Also, more practice problems.

Range problems usually have this format: given a list of values, we’d like to support the following operations:

  • Update value at index i
  • Compute f(a, b)

Or

  • Apply operation X to all elements in the range [a, b]
  • Get the value at index i

Whenever you see a problem like this you should think about Fenwick trees and there is a good chance it will be the data structure you need to solve the problem.

Problem & solution

Let’s take a look at the following problem from LeetCode Range Sum Query – Mutable.

If you know about Fenwick trees you’ll recognize the problem immediately and hopefully come up with a solution quickly. The problem follows the first pattern presented above. This is my solution:

class NumArray {
    private:
        vector<int> T;

        int lowestOneBit(int n) {
            return n & (-n);
        }

        void update(vector<int>& T, int index, int delta) {
            while (index < int(T.size())) {
                T[index] += delta;
                index += lowestOneBit(index);
            }
        }

        int read(vector<int>& T, int index) {
            int sum = 0;
            while (index > 0) {
                sum += T[index];
                index -= lowestOneBit(index);
            }
            return sum;
        }

    public:
        NumArray(vector<int> nums) {
            T.resize(nums.size() + 1);
            // Index the initial values
            for (size_t index = 0; index < nums.size(); index++) {
                update(T, index + 1, nums[index]);
            }
        }

        void update(int i, int newValue) {
            // Compute the current value at index i
            int value = read(T, i + 1) - read(T, i);

            // Update the BIT with the difference, not the new value
            update(T, i + 1, newValue - value);
        }

        int sumRange(int i, int j) {
            return read(T, j + 1) - read(T, i);
        }
};

Practice problems

Here you have some additional practice problems to hone your skills, enjoy!

References

This entry was posted in Posts. Bookmark the permalink.