C++ Coding Test Course, Calculating Segment Product

Understanding data structures and algorithms is an essential element for growth as a developer. C++ is a high-performance programming language that is widely used to solve algorithm problems, especially in coding tests. In this course, we will address the problem of ‘Calculating the Product of an Interval’ and explain various approaches to solve it.

Problem Definition

Let’s consider the problem of quickly calculating the product of a specified interval for a given array and several queries.

Problem:

There is a given integer array A and the number of queries Q.
A[i] represents the i-th element of the array, and 1 ≤ i ≤ N. Each query contains two numbers L and R, and the goal is to calculate the value of A[L] × A[L+1] × ... × A[R] when L ≤ R.

Input:

  • Size of the array N (1 ≤ N ≤ 105)
  • Integer array A[1...N] (1 ≤ A[i] ≤ 109)
  • Number of queries Q (1 ≤ Q ≤ 105)
  • Each query contains two integers L and R (1 ≤ L ≤ R ≤ N)

Output:

Print the product of the interval for each query, one per line.

Problem Approach

Several approaches can be considered to solve this problem.

The simplest method is to sequentially calculate the product of the given interval for each query.
However, this method is inefficient as it takes O(N * Q) time in the worst-case scenario.

The second approach is to use a Segment Tree.
The Segment Tree is effective for calculating sums, products, or maximum/minimum values for intervals in a short amount of time.

Each node of the Segment Tree stores the product of its segment, allowing us to calculate the interval product in O(log N) time.

Structure of the Segment Tree

The Segment Tree is structured like a binary tree, with each node storing information about a particular interval of the array.
Typically, a Segment Tree can perform the following main operations:

  1. Interval product query: query() function
  2. Element update: update() function

Final Code Implementation

Below is the C++ code for calculating the interval product using a Segment Tree:


#include <iostream>
#include <vector>
using namespace std;

// Definition of the Segment Tree class
class SegmentTree {
private:
    vector tree; // Storage for the tree
    int size; // Size of the original array
    
    // Function to calculate the product of a sub-array
    long long buildTree(const vector& arr, int node, int start, int end) {
        if(start == end) {
            return tree[node] = arr[start];
        }
        int mid = (start + end) / 2;
        return tree[node] = buildTree(arr, node*2, start, mid) * buildTree(arr, node*2+1, mid+1, end);
    }

public:
    // Constructor
    SegmentTree(const vector& arr) {
        size = arr.size();
        tree.resize(4 * size);
        buildTree(arr, 1, 0, size - 1);
    }

    // Function to get the product of a specific interval
    long long query(int node, int start, int end, int L, int R) {
        if(R < start || end < L) return 1; // Multiplication identity
        if(L <= start && end <= R) return tree[node]; // Range of the whole node
        int mid = (start + end) / 2;
        return query(node*2, start, mid, L, R) * query(node*2 + 1, mid + 1, end, L, R);
    }

    // Function callable from outside
    long long query(int L, int R) {
        return query(1, 0, size - 1, L, R);
    }
};

int main() {
    int N, Q;
    cin >> N; // Size of the array
    vector A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i]; // Input array elements
    }
    SegmentTree segtree(A); // Creating the Segment Tree

    cin >> Q; // Number of queries
    for(int i = 0; i < Q; i++) {
        int L, R;
        cin >> L >> R; // Input for query range
        cout << segtree.query(L - 1, R - 1) << endl; // Print result (converting to 0-based index)
    }
    return 0;
}

Code Explanation

  • buildTree() function is used to construct the Segment Tree.
  • query() function calculates the product for a given interval.
  • main() function receives inputs and outputs the processed interval products.

Time Complexity

The time to construct the Segment Tree is O(N), and the response time for each query is O(log N).
Therefore, the worst-case time complexity of the entire algorithm is O(N + Q log N).
This allows for efficient processing of large input data.

Conclusion

Choosing the appropriate data structure and algorithm for problems presented in coding tests is very important.
In this course, we addressed the problem of calculating the interval product using a Segment Tree, and explored what an efficient method entails.
I hope to enhance coding skills by solving algorithm problems and will continue to cover various topics in the future.