Description
Description
A buffer overflow occurs in the build function of prefix_sum_array.cpp when accessing elements of original_array. The error message indicates accessing index between 1 and 11 of an array with 11 elements, which leads to out-of-bounds access.
Expected behavior
The build() function should correctly construct a prefix sum array with these characteristics:
Proper Indexing:
Should use 0-based indexing for the input array (standard C++ practice)
Should not access any indices beyond original_array.size() - 1
Correct Preprocessing:
PSA[0] should remain 0 (neutral element for sum calculations)
PSA[1] should equal original_array[0]
PSA[i] should contain the sum of original_array[0] to original_array[i-1] for all valid indices
Final PSA size should be original_array.size() + 1
Actual behavior
Bug Location
The issue is in the build function in prefix_sum_array.cpp:
void build(std::vector<int64_t> original_array) {
for (int i = 1; i <= static_cast<int>(original_array.size()); i++) {
PSA.push_back(PSA[i - 1] + original_array[i]);
}
}
The loop condition i <= original_array.size() will cause i to reach size(), whereas the index range of a C++ vector is [0, size()-1]. As a result, original_array[i] will access invalid memory.
For example, the test array values has 11 elements (indices 0~10), but the loop will attempt to access values[11], leading to undefined behavior (UB).
### Steps to reproduce
_No response_
### Context
While this particular implementation doesn't immediately crash due to two mitigating factors (the test array starting with 0 and possible zero-padding in memory), this is still a dangerous bug that affects:
Code Reliability
The buffer overflow constitutes undefined behavior per C++ standards, meaning the program could behave unpredictably across different compilers/systems
Currently "works" only through sheer luck (memory padding zeros and test data coincidence)
### Additional information
_No response_