Cumulative Sum 2D (dp/cumulative-sum-2d.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2025-07-25 19:48:32+02:00
Include: #include "dp/cumulative-sum-2d.hpp"

For Cumulative Sum in 2 dimension. It cannot support modify. There are three main function.

add(x, y, z): Add z in (x, y)
build(): Build the cumulative sum. After finish add, it can be called.
query(sx, sy, gx, gy): Get the result in [sx, sy] ~ [gx, gy].

Code

#include <bits/stdc++.h>
using namespace std;
template <class T>
struct CumulativeSum2D {
    vector<vector<T> > data;

    CumulativeSum2D(int W, int H) : data(W + 1, vector<T>(H + 1, 0)) {}

    void add(int x, int y, T z) {
        ++x, ++y;
        if (x >= data.size() || y >= data[0].size()) return;
        data[x][y] += z;
    }

    void build() {
        for (int i = 1; i < data.size(); i++) {
            for (int j = 1; j < data[i].size(); j++) {
                data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
            }
        }
    }

    T query(int sx, int sy, int gx, int gy) const {
        /*求 [sx, sy] ~ [gx, gy] 整个矩形的和，都是闭区间 */
        gx++;
        gy++;
        return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
    }
};

#line 1 "dp/cumulative-sum-2d.hpp"
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct CumulativeSum2D {
    vector<vector<T> > data;

    CumulativeSum2D(int W, int H) : data(W + 1, vector<T>(H + 1, 0)) {}

    void add(int x, int y, T z) {
        ++x, ++y;
        if (x >= data.size() || y >= data[0].size()) return;
        data[x][y] += z;
    }

    void build() {
        for (int i = 1; i < data.size(); i++) {
            for (int j = 1; j < data[i].size(); j++) {
                data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
            }
        }
    }

    T query(int sx, int sy, int gx, int gy) const {
        /*求 [sx, sy] ~ [gx, gy] 整个矩形的和，都是闭区间 */
        gx++;
        gy++;
        return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
    }
};