C Programming Data Structures Segment Trees And Binary Indexed Trees Fenwick Tree Complete Guide

1. What is a Segment Tree and what are its primary uses?

Answer:
A Segment Tree is a data structure that allows answering range queries over an array efficiently while also supporting efficient updates to the array. It is a full binary tree where each node represents a contiguous segment of the array. The primary uses include finding the sum of elements in a range, finding the minimum or maximum in a range, and performing range updates.

2. How do you construct a Segment Tree in C?

Answer:
To construct a segment tree in C, you typically initialize a tree array (often 4 times the size of the input array). Here's a simple example for a sum query:

#include <stdio.h>
#include <stdlib.h>

void buildTree(int arr[], int tree[], int node, int start, int end) {
    if (start == end) {
        tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        buildTree(arr, tree, 2 * node, start, mid);
        buildTree(arr, tree, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int *tree = (int*)malloc(4 * n * sizeof(int));
    buildTree(arr, tree, 1, 0, n - 1);
    // tree is now constructed
    free(tree);
    return 0;
}

3. What is a Binary Indexed Tree (Fenwick Tree) and when is it used?

Answer:
A Binary Indexed Tree, or Fenwick Tree, is another data structure that can be used to manipulate cumulative frequency tables. It's one of the most efficient ways to maintain prefix sums of dynamic arrays. Its operations: querying the prefix sum, updating an element, and building the tree all run in O(log n) time.

4. How do you build a Binary Indexed Tree in C?

Answer:
Here's a basic example of initializing and updating a BIT:

#include <stdio.h>

void updateTree(int tree[], int n, int index, int delta){
    while(index <= n){
        tree[index] += delta;
        index += index & (-index);
    }
}

int queryTree(int tree[], int index){
    int sum = 0;
    while(index > 0){
        sum += tree[index];
        index -= index & (-index);
    }
    return sum;
}

int main(){
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int *tree = (int*)calloc(n + 1, sizeof(int));
    for(int i = 0; i < n; i++)
        updateTree(tree, n, i + 1, arr[i]);

    printf("Sum of first 3 elements: %d\n", queryTree(tree, 3));

    free(tree);
    return 0;
}

5. Which is more suitable between a Segment Tree and a Binary Indexed Tree for a problem involving prefix sums?

Answer:
For problems that involve only prefix sums (and point updates), a Binary Indexed Tree is usually more efficient because it has a simpler implementation and lower constant factors. However, Segment Trees are more suitable when you need to perform range queries and updates.

6. How would you handle a point update in a Segment Tree?

Answer:
ToUpdate a value in a segment tree, you need to propagate the change up the tree. Here's a sample update function:

void update(int tree[], int node, int start, int end, int idx, int val) {
    if (start == end) {
        // Leaf node
        arr[idx] += val;
        tree[node] += val;
    } else {
        int mid = (start + end) / 2;
        if(start <= idx && idx <= mid){
            // If idx is in the left child
            update(tree, 2 * node, start, mid, idx, val);
        } else {
            // If idx is in the right child
            update(tree, 2 * node + 1, mid + 1, end, idx, val);
        }
        // Internal node will have the sum of both of its children
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

7. How do you perform a range query in a Segment Tree?

Answer:
To query a range, you need to consider several cases to make sure you cover the range effectively:

int query(int tree[], int node, int start, int end, int l, int r) {
    if(r < start || end < l){
        // Range represented by a node is completely outside the given range
        return 0;
    }
    if(l <= start && end <= r){
        // Range represented by a node is completely inside the given range
        return tree[node];
    }
    // Segment tree is partly inside and partly outside the given range
    int mid = (start + end) / 2;
    int p1 = query(tree, 2 * node, start, mid, l, r);
    int p2 = query(tree, 2 * node + 1, mid + 1, end, l, r);
    return (p1 + p2);
}

8. How can you implement lazy propagation in a Segment Tree?

Answer:
Lazy propagation is used to defer updates to the underlying array, thus reducing the number of times a node is recursively updated:

void updateRange(int tree[], int lazy[], int node, int start, int end, int l, int r, int val) {
    if(lazy[node] != 0){
        tree[node] += (end - start + 1) * lazy[node];
        if(start != end){
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if(start > end || start > r || end < l){
        // Current segment is not within range [l, r]
        return;
    }
    if(start >= l && end <= r){
        // Segment is fully within range
        tree[node] += (end - start + 1) * val;
        if(start != end){
            // Not leaf node
            lazy[node * 2] += val;
            lazy[node * 2 + 1] += val;
        }
        return;
    }
    // Segment is partially within range
    int mid = (start + end) / 2;
    updateRange(tree, lazy, node * 2, start, mid, l, r, val);
    updateRange(tree, lazy, node * 2 + 1, mid + 1, end, l, r, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int queryRange(int tree[], int lazy[], int node, int start, int end, int l, int r) {
    if(start > end || start > r || end < l){
        return 0;
    }
    if(lazy[node] != 0) {
        // There are pending updates
        tree[node] += (end - start + 1) * lazy[node];
        if(start != end) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if(start >= l && end <= r){
        return tree[node];
    }
    int mid = (start + end) / 2;
    int p1 = queryRange(tree, lazy, node*2, start, mid, l, r);
    int p2 = queryRange(tree, lazy, node*2+1, mid+1, end, l, r);
    return (p1 + p2);
}

9. Can Segment Trees and Binary Indexed Trees be used for problems beyond sums and minimums?

Answer:
Yes, both Segment Trees and Binary Indexed Trees can be adapted to handle a variety of other queries and updates, such as finding the maximum, the greatest common divisor (GCD), the least common multiple (LCM), and even custom operations. However, more complex operations might require additional logic for handling updates and queries.

10. What are the time complexities associated with Segment Trees and Binary Indexed Trees?

Answer:

• Segment Trees:

  • Construction: O(n)
  • Range Query: O(log n)
  • Point Update: O(log n)
  • Range Update with Lazy Propagation: O(log n)

• Binary Indexed Trees (Fenwick Trees):

  • Construction: O(n log n) via repeated point updates
  • Prefix Sum Query: O(log n)
  • Point Update: O(log n)