[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