c++创建前缀和数组

在C++中，创建前缀和数组通常是为了高效地计算一个数组的累积求和，也被称为prefix sum。这个过程对于处理动态范围查询、区间和等问题非常有用。以下是创建前缀和数组的一般步骤：

1. 定义数组：首先，你需要一个与原始数据长度相同的数组`prefix_sum`，用于存储累积和。

int n; // 原始数据的元素数量
int prefix_sum[n];

2. 初始化：数组的每个元素通常是该位置索引处的数据值，除非是从0开始累积，那么初始时`prefix_sum[0] = arr[0];`，其余元素`prefix_sum[i] = prefix_sum[i - 1] + arr[i];`。

for (int i = 1; i < n; ++i) {
    prefix_sum[i] = prefix_sum[i - 1] + arr[i];
}

3. 使用前缀和：当你需要查询某个区间的和时，可以直接从`prefix_sum`数组中查找，而不需要再次遍历整个数组。例如，区间 `[l, r]` 的和是 `prefix_sum[r] - (l == 0 ? 0 : prefix_sum[l - 1])`。

int query(int l, int r) {
    return (r > 0) ? prefix_sum[r] - prefix_sum[l - 1] : prefix_sum[l];
}