枚举区间

一句话理解

枚举区间：枚举左端点、右端点。

为什么要学

区间题的暴力是 O(n²) 个子区间。

讲解

for l for r>=l 处理 a[l..r]。每个区间再求和若 O(n)，就变成 O(n³)，通常要前缀和降到 O(n²)。

这是前缀和、双指针的起点。

例子

for (int l = 1; l <= n; l++)
  for (int r = l; r <= n; r++)
    use(l, r);

所有连续子数组。

常见错误

• 每个区间 O(n) 求和变成 n³。
• r 从 1 开始而不是从 l。