Rectangle Sum of PointCloud
(Src/DataStructure/RectangleSum/RectangleSumOfPointCloud.hpp)

• View this file on GitHub
• Last update: 2025-04-25 15:47:36+09:00
• Include: #include "Src/DataStructure/RectangleSum/RectangleSumOfPointCloud.hpp"

概要

二次元平面上の $N$ 点 (重み付き)と $Q$ 個の矩形領域が与えられるので、各矩形領域内に属する点の重みの総和を計算する

ライブラリの使い方

template <class T, class U>
requires concepts::RSOPCQuery
std::vector<typename T::W> RectangleSumOfPointCloud(std::vector<T> ps, std::vector<U> qs) {

ps

重み付きの点のstd::vector

Tは基本的には以下をコピれば問題無いはず。

• Pが点の座標の型で、Wが重みの型を表す

struct Point {
    using P = int; 
    using W = long long;
    P x, y;
    W w;
};

Pは符号付き整数であることが期待される。

P型のメンバ変数x, yとW型のメンバ変数wが必要。

qs

矩形領域のstd::vector

基本的には以下をコピれば問題無い。Pが座標の型を表す。

// [l, r)x[d, u)
struct Rect {
    using P = int;
    int l, d, r, u;
};

Pは座標の型、psのPと型が一致している必要がある。

メンバ変数l, d, r, uが必要。左下の点が $(l, d)$ 、右上の点が $(r, u)$ となるようにする。

アルゴリズム

矩形クエリ $(l, d, r, u)$ は $(-\infty, -\infty, l, d), (-\infty, -\infty, r, d), (-\infty, -\infty, l, u), (-\infty, -\infty, r, u)$ の4つの矩形クエリの足し引きに帰着できる。

一方の軸について平面走査をすることにすると、一点更新・prefix和取得に帰着し、Fenwick Treeで処理できる。

• Fenwick Treeにのせる方の座標は座圧する。

時間計算量 $\Theta (N\log N + Q(\log Q + \log N))$ 、空間計算量 $\Theta (N + Q)$ でできる。

アルゴリズム・実装共に ei1333の日記 を参考にした。

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Required by

• Point Add Rectangle Sum (Src/DataStructure/RectangleSum/PointAddRectangleSum.hpp)

Verified with

• Test/AtCoder/abc136_f.test.cpp
• Test/LC/point_add_rectangle_sum/PointAddRectangleSum.test.cpp
• Test/LC/rectangle_sum.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"

#include <algorithm>
#include <concepts>
#include <utility>
#include <vector>
#include <type_traits>

namespace zawa {

namespace concepts {

template <class T>
concept Point = requires (T p) {
    typename T::P;
    typename T::W;
    { p.x } -> std::same_as<typename T::P&>;
    { p.y } -> std::same_as<typename T::P&>;
    { p.w } -> std::same_as<typename T::W&>;
};

template <class T>
concept Rectangle = requires (T r) {
    typename T::P;
    { r.l } -> std::same_as<typename T::P&>;
    { r.d } -> std::same_as<typename T::P&>;
    { r.r } -> std::same_as<typename T::P&>;
    { r.u } -> std::same_as<typename T::P&>;
};

template <class T, class U>
concept RSOPCQuery = Point<T> and Rectangle<U> and std::same_as<typename T::P, typename U::P>;

} // namespace concepts

template <class T, class U>
std::vector<typename T::W> RectangleSumOfPointCloud(std::vector<T> ps, std::vector<U> qs) requires concepts::RSOPCQuery<T, U> {
    using P = typename T::P;
    using W = typename T::W;
    usize n{ps.size()}, q{qs.size()};
    std::vector<P> xs(n);
    for (usize i{} ; i < n ; i++) xs[i] = ps[i].x;
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
    std::sort(ps.begin(), ps.end(), [&](const auto& L, const auto& R) -> bool {
            return L.y < R.y;
            });
    using Q = std::pair<P, usize>;
    std::vector<Q> query(qs.size() << 1);
    for (usize i{} ; i < qs.size() ; i++) {
        qs[i].l = (P)std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), qs[i].l));
        qs[i].r = (P)std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), qs[i].r));
        query[i] = std::pair{qs[i].d, i};
        query[i + q] = std::pair{qs[i].u, i + q};
    }
    std::sort(query.begin(), query.end());
    std::vector<W> fen(xs.size() + 1), res(qs.size());
    auto pref{[&](i32 r) -> W {
        W sum{};
        for ( ; r ; r -= r & -r) sum += fen[r];
        return sum;
    }};
    for (usize i{}, j{} ; i < query.size() ; i++) {
        while (j < n and ps[j].y < query[i].first) {
            i32 x{(i32)std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), ps[j].x))}; 
            for ( x++ ; (usize)x < fen.size() ; x += x & -x) fen[x] += ps[j].w;
            j++;
        }
        usize idx{query[i].second};
        if (idx < q) {
            res[idx] += pref(qs[idx].l) - pref(qs[idx].r);
        }
        else {
            idx -= q;
            res[idx] += -pref(qs[idx].l) + pref(qs[idx].r);
        }
    } 
    return res;
}

} // namespace zawa

#line 2 "Src/DataStructure/RectangleSum/RectangleSumOfPointCloud.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/DataStructure/RectangleSum/RectangleSumOfPointCloud.hpp"

#include <algorithm>
#include <concepts>
#include <utility>
#include <vector>
#include <type_traits>

namespace zawa {

namespace concepts {

template <class T>
concept Point = requires (T p) {
    typename T::P;
    typename T::W;
    { p.x } -> std::same_as<typename T::P&>;
    { p.y } -> std::same_as<typename T::P&>;
    { p.w } -> std::same_as<typename T::W&>;
};

template <class T>
concept Rectangle = requires (T r) {
    typename T::P;
    { r.l } -> std::same_as<typename T::P&>;
    { r.d } -> std::same_as<typename T::P&>;
    { r.r } -> std::same_as<typename T::P&>;
    { r.u } -> std::same_as<typename T::P&>;
};

template <class T, class U>
concept RSOPCQuery = Point<T> and Rectangle<U> and std::same_as<typename T::P, typename U::P>;

} // namespace concepts

template <class T, class U>
std::vector<typename T::W> RectangleSumOfPointCloud(std::vector<T> ps, std::vector<U> qs) requires concepts::RSOPCQuery<T, U> {
    using P = typename T::P;
    using W = typename T::W;
    usize n{ps.size()}, q{qs.size()};
    std::vector<P> xs(n);
    for (usize i{} ; i < n ; i++) xs[i] = ps[i].x;
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
    std::sort(ps.begin(), ps.end(), [&](const auto& L, const auto& R) -> bool {
            return L.y < R.y;
            });
    using Q = std::pair<P, usize>;
    std::vector<Q> query(qs.size() << 1);
    for (usize i{} ; i < qs.size() ; i++) {
        qs[i].l = (P)std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), qs[i].l));
        qs[i].r = (P)std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), qs[i].r));
        query[i] = std::pair{qs[i].d, i};
        query[i + q] = std::pair{qs[i].u, i + q};
    }
    std::sort(query.begin(), query.end());
    std::vector<W> fen(xs.size() + 1), res(qs.size());
    auto pref{[&](i32 r) -> W {
        W sum{};
        for ( ; r ; r -= r & -r) sum += fen[r];
        return sum;
    }};
    for (usize i{}, j{} ; i < query.size() ; i++) {
        while (j < n and ps[j].y < query[i].first) {
            i32 x{(i32)std::distance(xs.begin(), std::lower_bound(xs.begin(), xs.end(), ps[j].x))}; 
            for ( x++ ; (usize)x < fen.size() ; x += x & -x) fen[x] += ps[j].w;
            j++;
        }
        usize idx{query[i].second};
        if (idx < q) {
            res[idx] += pref(qs[idx].l) - pref(qs[idx].r);
        }
        else {
            idx -= q;
            res[idx] += -pref(qs[idx].l) + pref(qs[idx].r);
        }
    } 
    return res;
}

} // namespace zawa

Back to top page