前缀和 - 南叶の小窝

南叶酱

摸鱼ing...

统计加载中...

公告

评论不能用！！！其他里的东西暂时还没改，不是我的！！问题反馈和建议请加qq420883290 主页很乱，想看相关内容请看分类

Learn More

246 字

1 分钟

前缀和

2025-11-04

算法

统计加载中...

基本的代码

1
  vector<int> pre(n + 1, 0);
2
    for (int i = 0; i < n; i++) {
3
        pre[i + 1] = pre[i] + o[i];
4
    }

主要是在O（1）用来算一段区间的和

二维前缀和#

1
ll a[N][N], pre[N][N];
2
void solve()
3
{
4
    ll n, m, c;
5
    cin >> n >> m >> c;
6
    for(int i = 1; i <= n; ++i)
7
        for(int j = 1; j <= m; ++j)
8
         cin >> a[i][j];
9
    for(int i = 1; i <= n; ++i)
10
        for(int j = 1; j <= m; ++j)
11
         pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + a[i][j];
12
    ll ans = -INF;
13
    ll x = 0, y = 0;
14
    for(int i = 1; i <= n; ++i)
15
    {
16
        for(int j = 1; j <= m; ++j)
17
        {
18
            if(i + c - 1 > n || j + c - 1 > m)
19
                continue;
20
            if(ans < pre[i + c - 1][j + c - 1] - pre[i + c - 1][j - 1] - pre[i - 1][j +c - 1] + pre[i - 1][j - 1])
21
            {
22
                ans = pre[i + c - 1][j + c - 1] - pre[i + c - 1][j - 1] - pre[i - 1][j+ c - 1] + pre[i - 1][j - 1];
23
                x = i, y = j;
24
            }
25
        }
26
    }
27
    cout << x << " " << y << '\n';
28
}