Cumulative Sum (1D, 2D, 3D)
(ds/range_query/cumulative_sum.hpp)

View this file on GitHub
Last update: 2026-07-03 14:46:35+09:00
Include: #include "ds/range_query/cumulative_sum.hpp"

Overview

CumulativeSum1D, CumulativeSum2D, and CumulativeSum3D preprocess static arrays so that interval, rectangle, and cuboid sums can be answered in constant time. Indices are zero-based and every range is half-open.

This header lives in ds/range_query/ because it constructs a reusable query object. One-shot sequence algorithms live in algo/sequence/, and small contest helpers live in utilities/.

CumulativeSum<T> is an alias for CumulativeSum1D<T>.

The multidimensional classes store their prefix tables in contiguous memory. The input is interpreted as row-major values[y][x] in 2D and values[z][y][x] in 3D. Input rows and planes must form a rectangular grid.

Template Requirements

T{} must be the additive identity.
T must support addition and subtraction, with the usual additive-group laws. Integer, floating-point, and modular-number types are typical choices.

As with any cumulative sum, choose T large enough to hold every prefix sum.

Methods

`CumulativeSum1D<T>`

Method	Description	Complexity
`CumulativeSum1D()`	Constructs an empty array.	$O(1)$
`CumulativeSum1D(const std::vector<T>& values)`	Builds cumulative sums for `values`.	$O(N)$ time and space
`int size() const`	Returns $N$.	$O(1)$
`bool empty() const`	Returns whether $N = 0$.	$O(1)$
`T sum(int r) const`	Returns the sum of `[0, r)`.	$O(1)$
`T sum(int l, int r) const`	Returns the sum of `[l, r)`.	$O(1)$

`CumulativeSum2D<T>`

Method	Description	Complexity
`CumulativeSum2D()`	Constructs an empty grid.	$O(1)$
`CumulativeSum2D(const std::vector<std::vector<T>>& values)`	Builds cumulative sums for an $H \times W$ grid.	$O(HW)$ time and space
`int height() const`	Returns $H$.	$O(1)$
`int width() const`	Returns $W$.	$O(1)$
`bool empty() const`	Returns whether any dimension is zero.	$O(1)$
`T sum(int y, int x) const`	Returns the sum of `[0, y) x [0, x)`.	$O(1)$
`T sum(int y1, int y2, int x1, int x2) const`	Returns the sum of `[y1, y2) x [x1, x2)`.	$O(1)$

`CumulativeSum3D<T>`

Method	Description	Complexity
`CumulativeSum3D()`	Constructs an empty grid.	$O(1)$
`CumulativeSum3D(const std::vector<std::vector<std::vector<T>>>& values)`	Builds cumulative sums for a $D \times H \times W$ grid.	$O(DHW)$ time and space
`int depth() const`	Returns $D$.	$O(1)$
`int height() const`	Returns $H$.	$O(1)$
`int width() const`	Returns $W$.	$O(1)$
`bool empty() const`	Returns whether any dimension is zero.	$O(1)$
`T sum(int z, int y, int x) const`	Returns the sum of `[0, z) x [0, y) x [0, x)`.	$O(1)$
`T sum(int z1, int z2, int y1, int y2, int x1, int x2) const`	Returns the sum of `[z1, z2) x [y1, y2) x [x1, x2)`.	$O(1)$

All query bounds are checked with assertions.

Example

#include "ds/range_query/cumulative_sum.hpp"

#include <iostream>
#include <vector>

int main() {
    std::vector<std::vector<int>> grid(2, std::vector<int>(3));
    grid[0][0] = 1;
    grid[0][1] = 2;
    grid[0][2] = 3;
    grid[1][0] = 4;
    grid[1][1] = 5;
    grid[1][2] = 6;

    m1une::ds::CumulativeSum2D<int> sums(grid);

    // Rows [0, 2), columns [1, 3): 2 + 3 + 5 + 6 = 16.
    std::cout << sums.sum(0, 2, 1, 3) << '\n';
}

Verified with

verify/ds/range_query/cumulative_sum.test.cpp

Code

#ifndef M1UNE_DS_CUMULATIVE_SUM_HPP
#define M1UNE_DS_CUMULATIVE_SUM_HPP 1

#include <cassert>
#include <cstddef>
#include <vector>

namespace m1une {
namespace ds {

// Static one-dimensional cumulative sums.
template <typename T>
struct CumulativeSum1D {
   private:
    std::vector<T> _prefix;

   public:
    CumulativeSum1D() : _prefix(1, T{}) {}

    explicit CumulativeSum1D(const std::vector<T>& values)
        : _prefix(values.size() + 1, T{}) {
        for (std::size_t i = 0; i < values.size(); ++i) {
            _prefix[i + 1] = _prefix[i] + values[i];
        }
    }

    int size() const {
        return int(_prefix.size()) - 1;
    }

    bool empty() const {
        return size() == 0;
    }

    // Returns the sum of [0, r).
    T sum(int r) const {
        assert(0 <= r && r <= size());
        return _prefix[r];
    }

    // Returns the sum of [l, r).
    T sum(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        return _prefix[r] - _prefix[l];
    }
};

// The unsuffixed name is an alias for the one-dimensional structure.
template <typename T>
using CumulativeSum = CumulativeSum1D<T>;

// Static two-dimensional cumulative sums over a rectangular row-major grid.
template <typename T>
struct CumulativeSum2D {
   private:
    int _height;
    int _width;
    std::vector<T> _prefix;

    std::size_t index(int y, int x) const {
        return std::size_t(y) * std::size_t(_width + 1) + std::size_t(x);
    }

   public:
    CumulativeSum2D() : _height(0), _width(0), _prefix(1, T{}) {}

    explicit CumulativeSum2D(const std::vector<std::vector<T>>& values)
        : _height(int(values.size())),
          _width(values.empty() ? 0 : int(values.front().size())),
          _prefix(
              std::size_t(_height + 1) * std::size_t(_width + 1), T{}
          ) {
        for (const auto& row : values) {
            assert(int(row.size()) == _width);
        }

        for (int y = 1; y <= _height; ++y) {
            for (int x = 1; x <= _width; ++x) {
                _prefix[index(y, x)] =
                    values[y - 1][x - 1] + _prefix[index(y - 1, x)]
                    + _prefix[index(y, x - 1)] - _prefix[index(y - 1, x - 1)];
            }
        }
    }

    int height() const {
        return _height;
    }

    int width() const {
        return _width;
    }

    bool empty() const {
        return _height == 0 || _width == 0;
    }

    // Returns the sum of [0, y) x [0, x).
    T sum(int y, int x) const {
        assert(0 <= y && y <= _height);
        assert(0 <= x && x <= _width);
        return _prefix[index(y, x)];
    }

    // Returns the sum of [y1, y2) x [x1, x2).
    T sum(int y1, int y2, int x1, int x2) const {
        assert(0 <= y1 && y1 <= y2 && y2 <= _height);
        assert(0 <= x1 && x1 <= x2 && x2 <= _width);
        return _prefix[index(y2, x2)] - _prefix[index(y1, x2)]
               - _prefix[index(y2, x1)] + _prefix[index(y1, x1)];
    }
};

// Static three-dimensional cumulative sums over a rectangular z-y-x grid.
template <typename T>
struct CumulativeSum3D {
   private:
    int _depth;
    int _height;
    int _width;
    std::vector<T> _prefix;

    std::size_t index(int z, int y, int x) const {
        return (std::size_t(z) * std::size_t(_height + 1) + std::size_t(y))
                   * std::size_t(_width + 1)
               + std::size_t(x);
    }

   public:
    CumulativeSum3D()
        : _depth(0), _height(0), _width(0), _prefix(1, T{}) {}

    explicit CumulativeSum3D(
        const std::vector<std::vector<std::vector<T>>>& values
    )
        : _depth(int(values.size())),
          _height(values.empty() ? 0 : int(values.front().size())),
          _width(
              values.empty() || values.front().empty()
                  ? 0
                  : int(values.front().front().size())
          ),
          _prefix(
              std::size_t(_depth + 1) * std::size_t(_height + 1)
                  * std::size_t(_width + 1),
              T{}
          ) {
        for (const auto& plane : values) {
            assert(int(plane.size()) == _height);
            for (const auto& row : plane) {
                assert(int(row.size()) == _width);
            }
        }

        for (int z = 1; z <= _depth; ++z) {
            for (int y = 1; y <= _height; ++y) {
                for (int x = 1; x <= _width; ++x) {
                    _prefix[index(z, y, x)] =
                        values[z - 1][y - 1][x - 1]
                        + _prefix[index(z - 1, y, x)]
                        + _prefix[index(z, y - 1, x)]
                        + _prefix[index(z, y, x - 1)]
                        - _prefix[index(z - 1, y - 1, x)]
                        - _prefix[index(z - 1, y, x - 1)]
                        - _prefix[index(z, y - 1, x - 1)]
                        + _prefix[index(z - 1, y - 1, x - 1)];
                }
            }
        }
    }

    int depth() const {
        return _depth;
    }

    int height() const {
        return _height;
    }

    int width() const {
        return _width;
    }

    bool empty() const {
        return _depth == 0 || _height == 0 || _width == 0;
    }

    // Returns the sum of [0, z) x [0, y) x [0, x).
    T sum(int z, int y, int x) const {
        assert(0 <= z && z <= _depth);
        assert(0 <= y && y <= _height);
        assert(0 <= x && x <= _width);
        return _prefix[index(z, y, x)];
    }

    // Returns the sum of [z1, z2) x [y1, y2) x [x1, x2).
    T sum(int z1, int z2, int y1, int y2, int x1, int x2) const {
        assert(0 <= z1 && z1 <= z2 && z2 <= _depth);
        assert(0 <= y1 && y1 <= y2 && y2 <= _height);
        assert(0 <= x1 && x1 <= x2 && x2 <= _width);
        return _prefix[index(z2, y2, x2)] - _prefix[index(z1, y2, x2)]
               - _prefix[index(z2, y1, x2)] - _prefix[index(z2, y2, x1)]
               + _prefix[index(z1, y1, x2)] + _prefix[index(z1, y2, x1)]
               + _prefix[index(z2, y1, x1)] - _prefix[index(z1, y1, x1)];
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_CUMULATIVE_SUM_HPP

#line 1 "ds/range_query/cumulative_sum.hpp"



#include <cassert>
#include <cstddef>
#include <vector>

namespace m1une {
namespace ds {

// Static one-dimensional cumulative sums.
template <typename T>
struct CumulativeSum1D {
   private:
    std::vector<T> _prefix;

   public:
    CumulativeSum1D() : _prefix(1, T{}) {}

    explicit CumulativeSum1D(const std::vector<T>& values)
        : _prefix(values.size() + 1, T{}) {
        for (std::size_t i = 0; i < values.size(); ++i) {
            _prefix[i + 1] = _prefix[i] + values[i];
        }
    }

    int size() const {
        return int(_prefix.size()) - 1;
    }

    bool empty() const {
        return size() == 0;
    }

    // Returns the sum of [0, r).
    T sum(int r) const {
        assert(0 <= r && r <= size());
        return _prefix[r];
    }

    // Returns the sum of [l, r).
    T sum(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        return _prefix[r] - _prefix[l];
    }
};

// The unsuffixed name is an alias for the one-dimensional structure.
template <typename T>
using CumulativeSum = CumulativeSum1D<T>;

// Static two-dimensional cumulative sums over a rectangular row-major grid.
template <typename T>
struct CumulativeSum2D {
   private:
    int _height;
    int _width;
    std::vector<T> _prefix;

    std::size_t index(int y, int x) const {
        return std::size_t(y) * std::size_t(_width + 1) + std::size_t(x);
    }

   public:
    CumulativeSum2D() : _height(0), _width(0), _prefix(1, T{}) {}

    explicit CumulativeSum2D(const std::vector<std::vector<T>>& values)
        : _height(int(values.size())),
          _width(values.empty() ? 0 : int(values.front().size())),
          _prefix(
              std::size_t(_height + 1) * std::size_t(_width + 1), T{}
          ) {
        for (const auto& row : values) {
            assert(int(row.size()) == _width);
        }

        for (int y = 1; y <= _height; ++y) {
            for (int x = 1; x <= _width; ++x) {
                _prefix[index(y, x)] =
                    values[y - 1][x - 1] + _prefix[index(y - 1, x)]
                    + _prefix[index(y, x - 1)] - _prefix[index(y - 1, x - 1)];
            }
        }
    }

    int height() const {
        return _height;
    }

    int width() const {
        return _width;
    }

    bool empty() const {
        return _height == 0 || _width == 0;
    }

    // Returns the sum of [0, y) x [0, x).
    T sum(int y, int x) const {
        assert(0 <= y && y <= _height);
        assert(0 <= x && x <= _width);
        return _prefix[index(y, x)];
    }

    // Returns the sum of [y1, y2) x [x1, x2).
    T sum(int y1, int y2, int x1, int x2) const {
        assert(0 <= y1 && y1 <= y2 && y2 <= _height);
        assert(0 <= x1 && x1 <= x2 && x2 <= _width);
        return _prefix[index(y2, x2)] - _prefix[index(y1, x2)]
               - _prefix[index(y2, x1)] + _prefix[index(y1, x1)];
    }
};

// Static three-dimensional cumulative sums over a rectangular z-y-x grid.
template <typename T>
struct CumulativeSum3D {
   private:
    int _depth;
    int _height;
    int _width;
    std::vector<T> _prefix;

    std::size_t index(int z, int y, int x) const {
        return (std::size_t(z) * std::size_t(_height + 1) + std::size_t(y))
                   * std::size_t(_width + 1)
               + std::size_t(x);
    }

   public:
    CumulativeSum3D()
        : _depth(0), _height(0), _width(0), _prefix(1, T{}) {}

    explicit CumulativeSum3D(
        const std::vector<std::vector<std::vector<T>>>& values
    )
        : _depth(int(values.size())),
          _height(values.empty() ? 0 : int(values.front().size())),
          _width(
              values.empty() || values.front().empty()
                  ? 0
                  : int(values.front().front().size())
          ),
          _prefix(
              std::size_t(_depth + 1) * std::size_t(_height + 1)
                  * std::size_t(_width + 1),
              T{}
          ) {
        for (const auto& plane : values) {
            assert(int(plane.size()) == _height);
            for (const auto& row : plane) {
                assert(int(row.size()) == _width);
            }
        }

        for (int z = 1; z <= _depth; ++z) {
            for (int y = 1; y <= _height; ++y) {
                for (int x = 1; x <= _width; ++x) {
                    _prefix[index(z, y, x)] =
                        values[z - 1][y - 1][x - 1]
                        + _prefix[index(z - 1, y, x)]
                        + _prefix[index(z, y - 1, x)]
                        + _prefix[index(z, y, x - 1)]
                        - _prefix[index(z - 1, y - 1, x)]
                        - _prefix[index(z - 1, y, x - 1)]
                        - _prefix[index(z, y - 1, x - 1)]
                        + _prefix[index(z - 1, y - 1, x - 1)];
                }
            }
        }
    }

    int depth() const {
        return _depth;
    }

    int height() const {
        return _height;
    }

    int width() const {
        return _width;
    }

    bool empty() const {
        return _depth == 0 || _height == 0 || _width == 0;
    }

    // Returns the sum of [0, z) x [0, y) x [0, x).
    T sum(int z, int y, int x) const {
        assert(0 <= z && z <= _depth);
        assert(0 <= y && y <= _height);
        assert(0 <= x && x <= _width);
        return _prefix[index(z, y, x)];
    }

    // Returns the sum of [z1, z2) x [y1, y2) x [x1, x2).
    T sum(int z1, int z2, int y1, int y2, int x1, int x2) const {
        assert(0 <= z1 && z1 <= z2 && z2 <= _depth);
        assert(0 <= y1 && y1 <= y2 && y2 <= _height);
        assert(0 <= x1 && x1 <= x2 && x2 <= _width);
        return _prefix[index(z2, y2, x2)] - _prefix[index(z1, y2, x2)]
               - _prefix[index(z2, y1, x2)] - _prefix[index(z2, y2, x1)]
               + _prefix[index(z1, y1, x2)] + _prefix[index(z1, y2, x1)]
               + _prefix[index(z2, y1, x1)] - _prefix[index(z1, y1, x1)];
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Cumulative Sum (1D, 2D, 3D)
(ds/range_query/cumulative_sum.hpp)

Overview

Template Requirements

Methods

`CumulativeSum1D<T>`

`CumulativeSum2D<T>`

`CumulativeSum3D<T>`

Example

Verified with

Code

Cumulative Sum (1D, 2D, 3D) (ds/range_query/cumulative_sum.hpp)

Overview

Template Requirements

Methods

CumulativeSum1D<T>

CumulativeSum2D<T>

CumulativeSum3D<T>

Example

Verified with

Code

Cumulative Sum (1D, 2D, 3D)
(ds/range_query/cumulative_sum.hpp)

`CumulativeSum1D<T>`

`CumulativeSum2D<T>`

`CumulativeSum3D<T>`