DEV Community: Wengao Ye

Fenwick Tree vs Segment Tree

Wengao Ye — Mon, 13 Mar 2023 01:24:42 +0000

When it comes to solving range-based queries on an array, two of the most commonly used data structures are Fenwick Tree and Segment Tree. Both data structures offer efficient solutions to range-based queries and can be used interchangeably in many cases. However, there are some key differences between the two that can affect their suitability for different use cases.

In this article, we'll take a closer look at both data structures, their strengths and weaknesses, and when you might choose one over the other.

What is a Fenwick Tree

Fenwick Tree, also known as Binary Indexed Tree (BIT), is a data structure that allows efficient querying and updating of prefix sums in an array. The key feature of a Fenwick tree is that it uses a binary representation of indices to compute prefix sums. It has a space complexity of O(N) and a time complexity of O(log N) for both range queries and point updates.

BIT is easy to implement and is particularly useful for solving problems that require cumulative frequency or sum queries, such as finding the sum of all elements in a given range. It works by storing the cumulative frequency of elements up to a certain index i in the i-th position of the BIT array.

How to implement a BIT

To build a binary indexed tree, we start with an array of numbers A and create a new array T, where T[i] stores the sum of a range of elements from A that starts at i and includes the 2^(lowbit(i)) previous elements (where lowbit(i) is the least significant bit that is 1 in the binary representation of i).

For example, let A = [1, 2, 3, 4, 5, 6, 7, 8]. For convenience consideration, we assume the array is 1-indexed. Then we can build a binary indexed tree T as follows:

T[1] = A[1] = 1
T[2] = A[1] + A[2] = 3
T[3] = A[3] = 3
T[4] = A[1] + A[2] + A[3] + A[4] = 10
T[5] = A[5] = 5
T[6] = A[5] + A[6] = 11
T[7] = A[7] = 7
T[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8] = 36

A typical implementation of BIT:

public class FenwickTree {
    private final int[] tree;

    public FenwickTree(int n) {
        this.tree = new int[n];
    }

    public void add(int idx, int val) {
        for (int i = idx; i < tree.length; i += lowbit(i)) {
            tree[i] += val;
        }
    }

    public int query(int idx) {
        int sum = 0;
        for (int i = idx; i > 0; i -= lowbit(i)) {
            sum += tree[i];
        }
        return sum;
    }

    private int lowbit(int x) {
        return x & -x;
    }
}

If we want to initialize the BIT from an input array, we can do something like:

void someMethod(int[] nums) {
    FenwickTree tree = new FenwickTree(nums.length + 1);
    for (int i = 0; i < nums.length; ++i) {
        tree.add(i + 1, nums[i]);
    }

    // use the tree to do further queries and updates.
    // ...
}

What is a Segment Tree

Compared to Fenwick Tree, Segment Tree is a more general-purpose data structure used to efficiently perform range-based queries and range updates on an array. It is an extension of the concept of Fenwick Tree and can handle more complex queries/updates. Like a Fenwick tree, a segment tree is also based on the divide-and-conquer approach, where a problem is recursively divided into subproblems until a base case is reached. Segment Tree has a space complexity of O(N) and a time complexity of O(log N) for both range queries, point updates and range updates.

If you are interested in more details regarding the segment tree, please refer to the following three articles:

Comparison

Fenwick Tree is generally simpler to implement than Segment Tree and can be used to solve problems that only require cumulative frequency or sum queries. It is also more space-efficient, with a space complexity of O(N) compared to O(2N) for Segment Tree (NOTE: If we use a physical binary tree structure to implement, the space complexity is O(2N); If we use a bounded array to implement, the space complexity is O(4N). For more details, please refer to: Efficiently Implement a Basic Segment Tree).

Segment Tree, on the other hand, is more general-purpose and can be used to solve a wider range of problems. It is also more flexible in terms of the operations it can perform, with support for a wider range of operations than Fenwick Tree. Especially, Segment Tree with Lazy Propagation can support range updates in O(log N) time, while Fenwick Tree only supports point updates.

Another important difference between the two is the time complexity of point updates. While both data structures have a time complexity of O(log N) for point updates, Fenwick Tree is generally faster in practice due to its simpler implementation and better cache performance.

Put simply, if a problem can be solved by a Fenwick Tree, then it can certainly be solved by a Segment Tree as well. But the reverse is not necessarily true. However, due to the simpler implementation and faster point updates in practice, Fenwick Tree is preferable over Segment Tree if a problem can be solved by them.

Application

Now let's see how to use Fenwick Tree or Segment Tree to solve a practical problem.

Problem

Given an integer array nums, handle multiple queries of the following types:

Update the value of an element in nums.

Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

NumArray(int[] nums) initializes the object with the integer array nums.
void update(int index, int val) updates the value of nums[index] to be val.
int sumRange(int left, int right) returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Solution using Fenwick Tree

public class NumArray {
    private final int[] nums;
    private final int[] tree;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.tree = new int[nums.length + 1];
        for (int i = 0; i < nums.length; ++i) {
            add(i + 1, nums[i]);
        }
    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        add(index + 1, delta);
    }

    public int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }

    private void add(int idx, int val) {
        for (int i = idx; i < tree.length; i += lowbit(i)) {
            tree[i] += val;
        }
    }

    private int query(int idx) {
        int sum = 0;
        for (int i = idx; i > 0; i -= lowbit(i)) {
            sum += tree[i];
        }
        return sum;
    }

    private int lowbit(int x) {
        return x & -x;
    }
}

Time complexity:

NumArray(int[] nums): O(N * log N)
void update(int index, int val): O(log N)
int sumRange(int left, int right): O(log N)

Solution using Segment Tree

public class NumArray {
    private final int[] tree;
    private final int len;

    public NumArray(int[] nums) {
        this.len = nums.length;
        this.tree = new int[nums.length * 4];
        this.buildTree(0, 0, nums.length - 1, nums);
    }

    public void update(int index, int val) {
        update(0, 0, len - 1, index, val);
    }

    public int sumRange(int left, int right) {
        return query(0, 0, len - 1, left, right);
    }

    private int query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) {
            return 0;
        }
        if (left <= start && end <= right) {
            return tree[node];
        }

        int sum = 0;
        int mid = start + (end - start) / 2;
        if (left <= mid) {
            sum += query(2 * node + 1, start, mid, left, right);
        }
        if (right > mid) {
            sum += query(2 * node + 2, mid + 1, end, left, right);
        }

        return sum;
    }

    private void update(int node, int start, int end, int idx, int val) {
        if (idx < start || end < idx) {
            return;
        }
        if (idx == start && idx == end) {
            tree[node] = val;
            return;
        }

        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        int mid = start + (end - start) / 2;

        if (idx <= mid) {
            update(leftChild, start, mid, idx, val);
        } else {
            update(rightChild, mid + 1, end, idx, val);
        }

        tree[node] = tree[leftChild] + tree[rightChild];
    }

    private void buildTree(int node, int start, int end, int[] nums) {
        if (start == end) {
            tree[node] = nums[start];
            return;
        }

        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        int mid = start + (end - start) / 2;

        buildTree(leftChild, start, mid, nums);
        buildTree(rightChild, mid + 1, end, nums);

        tree[node] = tree[leftChild] + tree[rightChild];
    }
}

Time complexity:

NumArray(int[] nums): O(N)
void update(int index, int val): O(log N)
int sumRange(int left, int right): O(log N)

Compile-Time Calculations using C++ Templates

Wengao Ye — Fri, 10 Mar 2023 16:27:53 +0000

C++ templates are a powerful tool that allows you to write generic code that can be used with different data types. One of the less commonly known features of C++ templates is the ability to perform compile-time calculations. This can be very useful in situations where you need to perform calculations that can be determined at compile-time, such as computing the size of an array or a constant value. In this article, we'll explore how to use C++ templates to do compile-time calculations.

What are Compile-Time Calculations?

Compile-time calculations are calculations that can be evaluated at compile-time, rather than at run-time. This means that the value of the calculation is known before the program runs. This can have several advantages, such as avoiding the overhead of performing the calculation at run-time and enabling the compiler to perform optimizations that may not be possible with run-time calculations.

Using C++ Templates for Compile-Time Calculations

To use C++ templates for compile-time calculations, we can define a template class or function that takes one or more arguments and performs the calculation. The result of the calculation is then used as a template parameter, which can be used in other parts of the program.

One commonly used example is to write a function that calculates the power of a number. The following implementation is frequently found in many sources:

template <signed B, unsigned N>
struct pow {
    static const int value = B * pow<B, N - 1>::value;
};

template <signed B>
struct pow<B, 0> {
    static const int value = 1;
};

int main() {
    constexpr auto res = pow<-3, 5>::value;
    std::cout << res << std::endl; // output: -243
    return 0;
}

In the above implementation, we can see that the base case for the recursion is when N is 0, in which case is handled by the specialization pow<B, 0>.

As we can see, it is tedious and non-intuitive to write a "duplicated" base case. With the help of constexpr keyword and if constexpr support from C++17, we can implement the power function in a more intuitive and concise way, just like writing a normal function.

template <signed B, unsigned N>
constexpr auto pow() {
    if constexpr (N == 0) {
        return 1;
    } else {
        return B * pow<B, N - 1>();
    }
}

int main() {
    constexpr auto res = pow<-3, 5>();
    std::cout << res << std::endl; // output: -243
    return 0;
}

Furthermore, we can easily evolve the above implementation to make it support the positive/negative power calculation of an integer or a float number. In addition, we can also optimize the algorithm to improve the time complexity from O(N) to O(log N).

template <typename T, signed N>
constexpr T pow(const T base) {
    if constexpr (N < 0) {
        return 1 / pow<T, -N>(base);
    }
    if constexpr (N == 0) {
        return 1;
    }
    if constexpr ((N & 1) == 0) {
        return pow<T, N / 2>(base * base);
    }
    return base * pow<T, N / 2>(base * base);
}

int main() {
    constexpr auto m = pow<int, 3>(-3);
    std::cout << m << std::endl; // output: -27

    constexpr auto n = pow<int, -3>(-3);
    std::cout << n << std::endl; // output: 0

    constexpr auto p = pow<double, 3>(2.5);
    std::cout << p << std::endl; // output: 15.625

    constexpr auto q = pow<double, -3>(2.0);
    std::cout << q << std::endl; // output: 0.125

    return 0;
}

Once again, all the calculations mentioned above will be done during the compile-time, which means that in the run-time the program just directly prints the final result.
Now, let's discuss a more complex problem to enhance our understanding of compile-time calculations using templates.

Using `constexpr` and templates to solve FizzBuzz problem at compile-time

FizzBuzz Problem

It is an easy problem that is commonly used in some tech interviews. The requirement is: write a program that can accept a positive integer N as input, then print out a series of numbers from 1 to N. More specifically, if the number is divisible by 3, then print fizz; if the number is divisible by 5, then print buzz; if the number is divisible by both 3 and 5, then print fizzbuzz.

Solution at run-time

It is trivial to write a solution to solve it at run-time. Below is an example:

std::string nFizzBuzz(const unsigned N) {
    if (N % 15 == 0) {
        return "fizzbuzz";
    } else if (N % 3 == 0) {
        return "fizz";
    } else if (N % 5 == 0) {
        return "buzz";
    }
    return std::to_string(N);
}

std::string fizzBuzz(const unsigned N) {
    if (N == 0) {
        return "";
    }

    std::string str = nFizzBuzzT(1);
    for (auto i = 2; i <= N; ++i) {
        str += ", " + nFizzBuzz(i);
    }
    return str;
}

When you call fizzBuzz(16), it will print out:

1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz, 16

Solution at compile-time

Implement auxiliary functions for compile-time use

In above solution, we use std::string and std::to_string which involves dynamic memory allocations under the hood. However, in C++17, heap allocations are not allowed in constexpr functions (Sidenote: in C++20, dynamic memory allocations are allowed, that means we can use std::vector and std::string in constexpr context). To solve this issue in C++17, we can manually implement the same functionality using char array.

First thing first, we can use a std::array<char, Size> to represent a string.

template <std::size_t Size>
using chars = std::array<char, Size>;

As we can see, in the naive solution, we use += for string cancatenation. So we also need to implement a concat for our chars. Since the underlying storage of chars is a fixed length array, we need to handle the array copy during the concatenation.

constexpr auto copy(const char* start, const char* end, char* dst) {
    while (start < end) {
        *dst++ = *start++;
    }
}

template <std::size_t N1, std::size_t N2>
constexpr auto concat(const chars<N1>& arr1, const chars<N2>& arr2) {
    chars<N1 + N2> res{};
    copy(arr1.begin(), arr1.end(), res.begin());
    copy(arr2.begin(), arr2.end(), res.begin() + N1);
    return res;
}

Then, we need to handle the std::to_string which can convert an integer into a string.

template <unsigned N>
constexpr auto to_chars() {
    constexpr char last_digit = '0' + N % 10;
    if constexpr (N >= 10) {
        return concat(to_chars<N / 10>(), chars<1>{last_digit});
    } else {
        return chars<1>{last_digit};
    }
}

Tackle the FizzBuzz problem at compile-time

Now with all the tools we have on hand, it is straightforward to translate the naive solution into a compile-time one:

template <unsigned N>
constexpr auto nFizzBuzz() {
    constexpr chars<4> FIZZ{'f', 'i', 'z', 'z'};
    constexpr chars<4> BUZZ{'b', 'u', 'z', 'z'};
    if constexpr (N % 15 == 0) {
        return concat(FIZZ, BUZZ);
    } else if constexpr (N % 3 == 0) {
        return FIZZ;
    } else if constexpr (N % 5 == 0) {
        return BUZZ;
    } else {
        return to_chars<N>();
    }
}

template <unsigned N>
constexpr auto fizzBuzz() {
    static_assert(N > 0);
    constexpr chars<2> SEPERATOR{',', ' '};
    if constexpr (N > 1) {
        return concat(fizzBuzz<N - 1>(), concat(SEPERATOR, nFizzBuzz<N>()));
    } else {
        return nFizzBuzz<N>();
    }
}

Conclusion

C++ templates can be used to perform compile-time calculations, which can be very useful in situations where you need to perform calculations that can be determined at compile-time. By defining a template class or function that takes one or more arguments and performs the calculation, you can compute the result at compile-time and use it as a template parameter in other parts of the program. With the help of constexpr keyword and if constexpr support, it is easier for us to write more intuitive and concise code in template metaprogramming. This can lead to more efficient and optimized code, as well as enabling new programming techniques that may not be possible with run-time calculations.