前缀和、双指针[滑动窗口]

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;  // 使用长整型防止溢出

const int N = 510;     // 矩阵最大尺寸

int n, m, k;
int p[N][N];           // 列前缀和数组
LL res = 0;            // 结果计数器

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    int a;
    // 构建列前缀和数组
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            scanf("%d", &a);
            p[i][j] = p[i - 1][j] + a;  // p[i][j]表示第j列前i行的和
        }

    // 双指针法统计子矩阵
    for (int i = 0; i < n; i ++)        // 上边界i
        for (int j = i + 1; j <= n; j ++) // 下边界j
        {
            for (int l = 1, r = 1, sum = 0; r <= m; r ++)  // 滑动窗口[l,r]
            {
                sum += p[j][r] - p[i][r];  // 增加右边界列的和
                while (sum > k)             // 超出阈值时收缩左边界
                {
                    sum -= p[j][l] - p[i][l];
                    l ++;
                }
                res += r - l + 1;          // 统计有效子矩阵数
            }
        }

    printf("%lld\n", res);

    return 0;
}

核心算法

1. 前缀和预处理

   • 构建列方向前缀和数组p[i][j]，表示第j列前i行的和

   • 公式：p[i][j] = p[i-1][j] + A[i][j]

2. 双指针滑动窗口

   • 固定上下边界i和j后，在列方向维护窗口[l,r]

   • 动态调整窗口使子矩阵和sum ≤ k

   • 有效子矩阵数计算：r - l + 1

分析过程

优化思路

1. 降维思想
   通过列前缀和将二维问题转化为一维区间和问题
   $$\text{子矩阵和} = \sum_{c=l}^{r} (p[j][c] - p[i][c])$$

2. 滑动窗口优化

   • 保持sum单调递增特性

   • 当sum > k时仅需移动左指针，无需重置右指针

   • 将内层复杂度从$O(m^2)$降为$O(m)$

结论

• 优化后复杂度：$O(n^2m)$，$500^3=1.25$亿次计算

• 效率提升：相比暴力法加速$500$倍

• 适用性：完美匹配题目数据范围限制

时间复杂度

应用场景

1. 二维区间统计

   • 适用于需要统计满足条件的矩形区域的问题

   • 典型场景：图像处理中的区域检测、矩阵数据分析

2. 滑动窗口变种

   • 可扩展至三维或多维情况

   • 类似问题：最大子矩阵和、带约束的子区域计数

错误示例：双指针循环时r重复计算，导致超时

    for (int i = 0; i < n; i ++)
        for (int j = i + 1; j <= n; j ++)
        {
            for (int l = 1, r = l, sum = 0; l <= m; l ++, r = l)
            {
                sum = p[j][l] - p[i][l];
                while (sum <= k && r <= m)
                {
                    r ++;
                    sum += p[j][r] - p[i][r];
                }
                res += r - l;
            }
        }

问题分析

给定的代码使用三重循环来统计满足条件的子矩阵数量。具体来说：

1. 外层两个循环固定子矩阵的上下边界i和j（从第i行到第j行）。
2. 内层循环使用双指针l和r来遍历列，计算子矩阵的和，并统计满足条件的子矩阵数量。

然而，这种方法在某些情况下会导致超时。我们需要分析其时间复杂度和具体实现，找出超时的原因。

时间复杂度分析

1. 外层循环：i从0到n-1，j从i+1到n，所以循环次数为O(n^2)。

2. 内层循环：l从1到m，对于每个l，r从l开始向右扩展，直到子矩阵和超过k。最坏情况下，r会遍历整个列，所以内层循环的时间复杂度为O(m^2)。

3. 总体时间复杂度：O(n^2 * m^2)。

对于n和m的最大值500，n^2 * m^2 = 500^4 = 62,500,000,000，这显然远远超过了时间限制，因此会导致超时。

具体实现问题

1. 双指针的移动方式：在内层循环中，对于每个l，r都是从l开始向右扩展，直到子矩阵和超过k。这意味着对于每个l，r都可能需要遍历从l到m的所有列，导致重复计算。

2. 没有利用滑动窗口的优化：正确的双指针方法应该利用滑动窗口的性质，保持l和r的单向移动，从而将内层循环的时间复杂度从O(m^2)降低到O(m)。