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.
Problems & solutions
For the first pattern, let’s take a look at the following LeetCode problem, Range Sum Query – Mutable.
If you know about Fenwick trees, you’ll recognize the problem immediately and hopefully come up with a solution quickly.
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); } };
As an example of the second pattern, let’s take a look at this other LeetCode problem, Shifting Letters II. We’re asked to execute a series of queries that consist in shifting all letters from index i
to index j
in one of two directions, then return the resulting string.
class Solution { private void update(int[] T, int idx, int delta) { while (idx < T.length) { T[idx] += delta; idx += (idx & -idx); } } private int read(int[] T, int idx) { int i = idx; int sum = 0; while (idx > 0) { sum += T[idx]; idx -= (idx & -idx); } return sum; } private int[] toIntCodes(String input) { int[] codes = new int[input.length()]; for (int i = 0; i < input.length(); i++) { codes[i] = input.charAt(i) - 'a'; } return codes; } private String toString(int[] codes) { char[] chars = new char[codes.length]; for (int i = 0; i < codes.length; i++) { chars[i] = (char)(codes[i] + 'a'); } return new String(chars); } public String shiftingLetters(String input, int[][] shifts) { int[] s = toIntCodes(input); int n = s.length; int[] T = new int[n+5]; for (var shift : shifts) { int start = shift[0] + 1; int end = shift[1] + 1; int delta = (shift[2] == 0) ? -1 : 1; // Add delta to [start, end] update(T, start, delta); update(T, end + 1, -delta); } final int B = 26; for (int i = 1; i <= n; i++) { // Return the cumulative sum of the segments `i` is responsible for. int v = read(T, i); int x = s[i-1] + v; x = x % B; while (x < 0) x += B; s[i-1] = x; } return toString(s); } }
Practice problems
Here you have some additional practice problems to hone your skills, enjoy!