[BUG]Bufferoverflow in range_queries/sparse_table_range_queries.cpp

[18781875724]

Description

I found a buffer overflow issue in range_queries/sparse_table_range_queries.cpp through static analysis. The problem occurs in two locations:
sparse_table_range_queries.cpp:61:26: Buffer overflow when accessing logs[n]
sparse_table_range_queries.cpp:86:13: Buffer overflow when accessing logs[end - beg + 1]
Problem Analysis:
The computeLogs function initializes the logs vector with size n (same as input array A)
However, the code later accesses logs[n] which is out of bounds (valid indices are 0 to n-1)
Similarly, when getMinimum(0, 4, ...) is called, it calculates end - beg + 1 = 5 but tries to access logs[5] when the vector size is only 5 (indices 0-4)

Expected behavior

Correct Sparse Table Construction:
The computeLogs function should generate a logarithm lookup table where:
logs[i] contains ⌊log₂(i)⌋ for all indices i from 1 to n (inclusive)

Actual behavior

Buffer Overflow in buildTable
When accessing logs[n] (line 61), the code reads out-of-bounds because logs is sized for indices 0 to n-1.
Buffer Overflow in getMinimum
For full-range queries (end - beg + 1 == n), logs[n] is accessed (line 86), causing another overflow.

Steps to reproduce

No response

Context

While testing the sparse table implementation, I discovered that:
Undetected Memory Unsafety
The code silently accesses out-of-bounds memory (e.g., logs[n]) without crashing in my test environment.
This makes it unreliable for production use, as it risks:
Reading garbage values → incorrect query results.
Memory corruption in long-running applications.

Additional information

No response

[18781875724]

Issue:
The original implementation of computeLogs could lead to an out-of-bounds access when computing logs up to n, since the loop runs up to i < n but accesses logs[i] (requiring n+1 elements).

Fix:

Changed logs size from n to n + 1 to accommodate indices 0 to n.

Adjusted loop condition from i < n to i <= n to ensure correct computation for all indices.

Corrected Code:

std::vector<T> computeLogs(const std::vector<T>& A) {
    int n = A.size();
    std::vector<T> logs(n + 1);  // Fix: Allocate n+1 elements
    logs[1] = 0;
    for (int i = 2; i <= n; i++) {  // Fix: Loop until i <= n
        logs[i] = logs[i / 2] + 1;
    }
    return logs;
}

Impact:

Avoids undefined behavior (e.g., crashes/incorrect results) when accessing logs[n].

Matches the mathematical intent of computing logs for all indices in [1, n].

Verification:
Tested with edge cases (e.g., n = 0, n = 1, n = power of 2), and results now align with expectations.