CC++ & Algorithm
算法可视化
入门执行逻辑

前缀和:快速求区间和

前缀和 pre[i] = 前 i 个元素之和。区间 [l, r] 的和 = pre[r+1] - pre[l],一次减法搞定,不用循环累加。

main.cpp第 2 行
1// 前缀和: pre[i] = a[0] + ... + a[i-1]
2int a[] = {3, 1, 4, 1, 5, 9};
3int pre[7]; pre[0] = 0;
4for (int i = 1; i <= 6; i++)
5 pre[i] = pre[i-1] + a[i-1];
6// 区间 [2, 4] 的和 = pre[5] - pre[2] = 14 - 4 = 10
变量表1 个变量
a[3, 1, 4, 1, 5, 9]
数组 a
比较交换已就位
3
0
1
1
4
2
1
3
5
4
9
5
1/10

原数组 a = [3, 1, 4, 1, 5, 9]

1 / 10