2D-Cumulative-Sum( $2$ 次元累積和) (dp/2d_cumulative_sum.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-03-16 17:39:42+09:00

なにこれ

$2$ 次元配列をもとに $2$ 次元累積和を求める．

コンストラクタ

• sum2d(m)：$2$ 次元配列 m をもとに $2$ 次元累積和のテーブルを構築する．

メンバ関数

• get(x, y)：$(x,y)$ までの累積和を返す．
• get(sx, sy, tx, ty)：$(sx,sy)$ から $(tx,ty)$ までの累積和を返す．$sx \leq tx,\ sy \leq ty$ であり，$(sx,sy)$ 側が開区間である．
• out()：累積和テーブルを出力する．

計算量

• コンストラクタ：$O(HW)$
• get()：$O(1)$
• out()：$O(HW)$

注意点

累積和テーブルを構築する際に，index が1つずれることに注意．(1次元累積和テーブルで table[0] に $0$ を格納するように，table[0][y] と table[x][0] に $0$ を格納している．)

Depends on

• 2D-Array( $2$ 次元配列) (structure/2d_array.cpp)

Verified with

• test/aoj_0560.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#include "../structure/2d_array.cpp"

template<typename T> struct sum2d {
private:
	const int H, W;
	v2d<T> table;

public:
	sum2d(v2d<T> &m) : H(m.size() + 1), W(m[0].size() + 1), table(H, W, 0) {
		for(int i = 1; i < H; i++)
			for(int j = 1; j < W; j++)
				table[i][j] = m[i - 1][j - 1] + table[i][j - 1] + table[i - 1][j] - table[i - 1][j - 1];
	}

	T get(int x, int y) {
		return table[x][y];
	}
	T get(int sx, int sy, int tx, int ty) {
		return table[tx][ty] - table[sx][ty] - table[tx][sy] + table[sx][sy];
	}

	void out() {
		table.out();
	}
};

#line 2 "dp/2d_cumulative_sum.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#line 2 "structure/2d_array.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> struct v2d {
private:
	vector<vector<T>> m;

public:
	v2d() {}
	v2d(int h, int w) : m(h, vector<T>(w)) {}
	v2d(int h, int w, const T &init) : m(h, vector<T>(w, init)) {}
	v2d(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}

	void assign(int h, int w) {
		m.assign(h, vector<T>(w));
	}
	void assign(int h, int w, const T init) {
		m.assign(h, vector<T>(w, init));
	}

	inline int size() const {
		return m.size();
	}

	void in() {
		for(vector<T> &v : m)
			for(T &val : v) cin >> val;
	}
	void in(int h, int w) {
		m.resize(h, vector<T>(w));
		in();
	}

	void out() {
		int h = m.size();
		for(vector<T> &v : m) {
			int sz = v.size();
			for(int j = 0; j < sz; j++) {
				cout << v[j] << (j == sz - 1 ? '\n' : ' ');
			}
		}
		cout << flush;
	}

	inline vector<T> &operator[](int idx) {
		assert(0 <= idx && idx < m.size());
		return m[idx];
	}

	bool rangeout(int x, int y) {
		if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true;
		return false;
	}
};
#line 10 "dp/2d_cumulative_sum.cpp"

template<typename T> struct sum2d {
private:
	const int H, W;
	v2d<T> table;

public:
	sum2d(v2d<T> &m) : H(m.size() + 1), W(m[0].size() + 1), table(H, W, 0) {
		for(int i = 1; i < H; i++)
			for(int j = 1; j < W; j++)
				table[i][j] = m[i - 1][j - 1] + table[i][j - 1] + table[i - 1][j] - table[i - 1][j - 1];
	}

	T get(int x, int y) {
		return table[x][y];
	}
	T get(int sx, int sy, int tx, int ty) {
		return table[tx][ty] - table[sx][ty] - table[tx][sy] + table[sx][sy];
	}

	void out() {
		table.out();
	}
};

Back to top page