Cumulative Sum 2D - 二次元累積和
(Library/DataStructure/CumulativeSum2D.hpp)

• View this file on GitHub
• Last update: 2026-02-08 19:33:09+09:00
• Include: #include "Library/DataStructure/CumulativeSum2D.hpp"

Cumulative Sum 2D - 二次元累積和

$H \times W$ の二次元配列 $A$ に対し、長方形領域の総和を効率的に計算するデータ構造です。

Function

Constructor

CumulativeSum2D(const int height, const int width, const T init_value = 0)

• 高さ $h$ = height、幅 $w$ = width の二次元累積和を初期化します。

制約

• $1 \le h, w \le 10^3$

計算量

• $\textrm{O}(hw)$

---

Set

void Set(const int y, const int x, const T value)

• 座標 $(y, x)$ に値 $v$ を代入します。$A_{y,x} \leftarrow v$
• 0-index で座標を指定します。

制約

• $0 \le y < h$
• $0 \le x < w$

計算量

• $\textrm{O}(1)$

---

Add (一点加算)

void Add(const int y, const int x, const T value)

• 座標 $(y, x)$ に値 $v$ を加算します。$A_{y,x} \leftarrow A_{y,x} + v$
• 0-index で座標を指定します。

制約

• $0 \le y < h$
• $0 \le x < w$

計算量

• $\textrm{O}(1)$

---

Add (領域加算)

void Add(const int y1, const int x1, const int y2, const int x2, const T value)

• 長方形領域 $[y_1, y_2] \times [x_1, x_2]$ に値 $v$ を加算します。
• 0-index、閉区間 で座標を指定します。

制約

• $0 \le y_1 \le y_2 < h$
• $0 \le x_1 \le x_2 < w$

計算量

• $\textrm{O}(1)$

---

Build

void Build()

• 累積和の構築を行います。
• Set() や Add() で値を設定した後、この関数を呼び出してください。

計算量

• $\textrm{O}(hw)$

---

Sum (矩形領域)

(1) T Sum(const int y, const int x) const
(2) T Sum(const int y1, const int x1, const int y2, const int x2) const

• (1) 長方形領域 $[0, y] \times [0, x]$ の総和を返します。
• (2) 長方形領域 $[y_1, y_2] \times [x_1, x_2]$ の総和を返します。
• 0-index、閉区間 で座標を指定します。

制約

• (1) $0 \le y < h$, $0 \le x < w$
• (2) $0 \le y_1 \le y_2 < h$, $0 \le x_1 \le x_2 < w$

計算量

• $\textrm{O}(1)$

---

Max

T Max() const

• 配列内の最大値を返します。

計算量

• $\textrm{O}(hw)$

---

Min

T Min() const

• 配列内の最小値を返します。

計算量

• $\textrm{O}(hw)$

---

operator[]

vector<T> &operator[](const int k)

• $k$ 行目の配列への参照を返します。
• 0-index でアクセスします。

制約

• $0 \le k < h$

計算量

• $\textrm{O}(1)$

---

Depends on

• Library/Common.hpp

Verified with

• verify/AOJ-0560.test.cpp
• verify/AOJ-DSL-5-B.test.cpp

Code

#include "../Common.hpp"

template<typename T = int32_t>
struct CumulativeSum2D{
    private:
    int height_, width_;
    vector<vector<T>> data_;

    void Validate(const int y, const int x) const {
        assert(0 <= y && y < height_ - 1);
        assert(0 <= x && x < width_ - 1);
    }

    public:
    CumulativeSum2D(const int height, const int width, const T init_value = 0) : height_(height + 1), width_(width + 1){
        data_.resize(height_);
        for(int i = 0; i < height_; ++i){
            data_.at(i).resize(width_, init_value);
        }
    }

    void Build(){
        for(int i = 1; i < height_; ++i){
            for(int j = 0; j < width_; ++j){
                data_[i][j] += data_[i - 1][j];
            }
        }
        for(int i = 0; i < height_; ++i){
            for(int j = 1; j < width_; ++j){
                data_[i][j] += data_[i][j - 1];
            }
        }
    }

    void Set(const int y, const int x, const T value){
        Validate(y, x);
        data_[y][x] = value;
    }

    void Add(const int y, const int x, const T value){
        Add(y, x, y, x, value);
    }

    void Add(const int y1, const int x1, const int y2, const int x2, const T value){
        Validate(y1, x1);
        Validate(y2, x2);
        data_[y1][x1] += value;
        data_[y2 + 1][x1] -= value;
        data_[y1][x2 + 1] -= value;
        data_[y2 + 1][x2 + 1] += value;
    }

    T Sum(const int y, const int x) const {
        Validate(y, x);
        return data_[y][x];
    }

    T Sum(const int y1, const int x1, const int y2, const int x2) const {
        Validate(y1, x1);
        Validate(y2, x2);
        T ret = Sum(y2, x2);
        if(y1 > 0) ret -= Sum(y1 - 1, x2);
        if(x1 > 0) ret -= Sum(y2, x1 - 1);
        if(y1 > 0 && x1 > 0) ret += Sum(y1 - 1, x1 - 1);
        return ret;
    }

    T Max() const {
        T ret = data_[0][0];
        for(int i = 0; i < height_; ++i){
            for(int j = 0; j < width_; ++j){
                ret = max(ret, data_[i][j]);
            }
        }
        return ret;
    }

    T Min() const {
        T ret = data_[0][0];
        for(int i = 0; i < height_; ++i){
            for(int j = 0; j < width_; ++j){
                ret = min(ret, data_[i][j]);
            }
        }
        return ret;
    }

    vector<T> &operator[](const int k){
        return data_.at(k);
    }
};

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 2 "Library/DataStructure/CumulativeSum2D.hpp"

template<typename T = int32_t>
struct CumulativeSum2D{
    private:
    int height_, width_;
    vector<vector<T>> data_;

    void Validate(const int y, const int x) const {
        assert(0 <= y && y < height_ - 1);
        assert(0 <= x && x < width_ - 1);
    }

    public:
    CumulativeSum2D(const int height, const int width, const T init_value = 0) : height_(height + 1), width_(width + 1){
        data_.resize(height_);
        for(int i = 0; i < height_; ++i){
            data_.at(i).resize(width_, init_value);
        }
    }

    void Build(){
        for(int i = 1; i < height_; ++i){
            for(int j = 0; j < width_; ++j){
                data_[i][j] += data_[i - 1][j];
            }
        }
        for(int i = 0; i < height_; ++i){
            for(int j = 1; j < width_; ++j){
                data_[i][j] += data_[i][j - 1];
            }
        }
    }

    void Set(const int y, const int x, const T value){
        Validate(y, x);
        data_[y][x] = value;
    }

    void Add(const int y, const int x, const T value){
        Add(y, x, y, x, value);
    }

    void Add(const int y1, const int x1, const int y2, const int x2, const T value){
        Validate(y1, x1);
        Validate(y2, x2);
        data_[y1][x1] += value;
        data_[y2 + 1][x1] -= value;
        data_[y1][x2 + 1] -= value;
        data_[y2 + 1][x2 + 1] += value;
    }

    T Sum(const int y, const int x) const {
        Validate(y, x);
        return data_[y][x];
    }

    T Sum(const int y1, const int x1, const int y2, const int x2) const {
        Validate(y1, x1);
        Validate(y2, x2);
        T ret = Sum(y2, x2);
        if(y1 > 0) ret -= Sum(y1 - 1, x2);
        if(x1 > 0) ret -= Sum(y2, x1 - 1);
        if(y1 > 0 && x1 > 0) ret += Sum(y1 - 1, x1 - 1);
        return ret;
    }

    T Max() const {
        T ret = data_[0][0];
        for(int i = 0; i < height_; ++i){
            for(int j = 0; j < width_; ++j){
                ret = max(ret, data_[i][j]);
            }
        }
        return ret;
    }

    T Min() const {
        T ret = data_[0][0];
        for(int i = 0; i < height_; ++i){
            for(int j = 0; j < width_; ++j){
                ret = min(ret, data_[i][j]);
            }
        }
        return ret;
    }

    vector<T> &operator[](const int k){
        return data_.at(k);
    }
};

Back to top page