前缀和
vector<long long> pre(n + 1, 0); for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i]; 区间 [l,r] 和 = pre[r + 1] - pre[l]。
差分
对区间 [l,r] 整体加 v:d[l] += v; d[r + 1] -= v; 最后对 d 做一次前缀和,就还原出每个位置的最终值。
加载中…
C++ 机试动画
本课导读
区间求和如果每次都重新累加就是 O(n)。前缀和让区间求和变成 O(1);差分让区间加变成 O(1)。这是机试高频套路。
vector<long long> pre(n + 1, 0); for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i]; 区间 [l,r] 和 = pre[r + 1] - pre[l]。
对区间 [l,r] 整体加 v:d[l] += v; d[r + 1] -= v; 最后对 d 做一次前缀和,就还原出每个位置的最终值。
把 C++ 做题手感练出来
这套课只讲机试最常用的 C++：输入输出、类型、数组、字符串和 STL。先把这些模板练熟，再去刷数据结构和算法题，效率会高很多。