## 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.

## 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

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

int sumRange(int i, int j) {
}
};```

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 x = s[i-1] + v;
x = x % B;
while (x < 0) x += B;
s[i-1] = x;
}
}
}
```

## Practice problems

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

Posted

in

by

Tags: