TB椰程 TypeBuddy 打字搭子

前缀和

CSP-J · 编程模板 · 片段 · cpp · 难度 2/5 · 共 272 字

预处理一次，区间求和变 O(1)

  • 前缀和
  • 区间

前置内容

正文

// ── 前缀和：区间和 O(1) 查询 ──
// sum[i] = a[1] + ... + a[i]
int sum[100005];
// sum[0] = 0 是边界哨兵
for (int i = 1; i <= n; i++) {
    // 当前和 = 之前的和 + 当前值
    sum[i] = sum[i - 1] + a[i];
}
// a[l..r] 区间和 = 前缀和相减
printf("%d", sum[r] - sum[l - 1]);
// 差分数组是它的逆运算
// 两者配合可做「区间改、区间查」

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK