Static Rectangle Sum
(data_structure/static_rectangle_sum.hpp)

• View this file on GitHub
• Last update: 2024-02-25 23:03:04+09:00
• Include: #include "data_structure/static_rectangle_sum.hpp"

説明

2次元平面に値があり、長方形内に含まれる値の和を求めるクエリを静的に処理する。点の個数を $N$ 、クエリの個数を $Q$ としたとき、計算量は $O((N + Q)\log{N})$

add_point(x, y, val)

$(x, y)$ に値 $val$ を加える。

add_query(l, d, r, u)

$[l, r) \times [d, u)$ の長方形内に含まれる値の和を求めるクエリを追加する。

run()

クエリを処理して、クエリを追加した順で処理結果を返す。

Depends on

• Compress (data_structure/compress.hpp)
• fenwick tree (data_structure/fenwick_tree.hpp)

Verified with

• test/data_structure/Static_Rectangle_Sum.test.cpp

Code

#pragma once

#include <array>
#include <tuple>
#include <vector>

#include "../data_structure/compress.hpp"
#include "../data_structure/fenwick_tree.hpp"

namespace ebi {

template <class S, class T> struct static_rectangle_sum {
  private:
  public:
    static_rectangle_sum() = default;

    void add_point(S x, S y, T val) {
        p.emplace_back(x, y, val);
        cp_x.add(x);
        cp_y.add(y);
    }

    void add_query(S l, S d, S r, S u) {
        q.push_back({l, d, r, u});
        cp_x.add(l);
        cp_x.add(r);
        cp_y.add(d);
        cp_y.add(u);
    }

    std::vector<T> run() {
        assert(is_first);
        is_first = false;
        cp_x.build();
        cp_y.build();
        std::vector ptable(cp_x.size(), std::vector<int>());
        std::vector qtable(cp_x.size(), std::vector(2, std::vector<int>()));
        for (int i = 0; auto [x, y, val] : p) {
            ptable[cp_x.get(x)].emplace_back(i);
            i++;
        }
        for (int i = 0; auto [l, d, r, u] : q) {
            qtable[cp_x.get(l)][0].emplace_back(i);
            qtable[cp_x.get(r)][1].emplace_back(i);
            i++;
        }
        std::vector<T> res(q.size(), 0);
        fenwick_tree<T> ftree(cp_y.size());
        for (int i = 0; i < cp_x.size(); i++) {
            for (int j = 0; j < 2; j++) {
                for (auto idx : qtable[i][j]) {
                    int d = q[idx][1], u = q[idx][3];
                    res[idx] +=
                        (j == 0 ? -1 : 1) * ftree.sum(cp_y.get(d), cp_y.get(u));
                }
            }
            for (auto idx : ptable[i]) {
                auto [x, y, val] = p[idx];
                ftree.add(cp_y.get(y), val);
            }
        }
        return res;
    }

  private:
    bool is_first = true;
    std::vector<std::tuple<S, S, T>> p;
    std::vector<std::array<S, 4>> q;
    compress<S> cp_x, cp_y;
};

}  // namespace ebi

#line 2 "data_structure/static_rectangle_sum.hpp"

#include <array>
#include <tuple>
#include <vector>

#line 2 "data_structure/compress.hpp"

#include <algorithm>
#include <cassert>
#line 6 "data_structure/compress.hpp"

namespace ebi {

template <class T> struct compress {
  private:
    std::vector<T> cp;

  public:
    compress() = default;

    compress(std::vector<T> cp_) : cp(cp_) {
        build();
    }

    void build() {
        std::sort(cp.begin(), cp.end());
        cp.erase(std::unique(cp.begin(), cp.end()), cp.end());
    }

    void add(const T &val) {
        cp.emplace_back(val);
    }

    int get(const T &val) const {
        return std::lower_bound(cp.begin(), cp.end(), val) - cp.begin();
    }

    int size() const {
        return cp.size();
    }

    bool find(const T &val) const {
        auto itr = std::lower_bound(cp.begin(), cp.end(), val);
        if (itr == cp.end())
            return false;
        else
            return *itr == val;
    }

    T val(int idx) const {
        assert(0 <= idx && idx < (int)cp.size());
        return cp[idx];
    }
};

}  // namespace ebi
#line 2 "data_structure/fenwick_tree.hpp"

#line 5 "data_structure/fenwick_tree.hpp"

namespace ebi {

template <class T> struct fenwick_tree {
  private:
    int n;
    std::vector<T> data;

  public:
    fenwick_tree(int _n) : n(_n), data(std::vector<T>(_n + 1, T(0))) {}

    void add(int i, T val) {
        i++;
        for (int x = i; x <= n; x += x & -x) {
            data[x] += val;
        }
    }

    T prefix_sum(int i) const {
        assert(0 <= i && i <= n);
        T ret = 0;
        for (int x = i; x > 0; x -= x & -x) {
            ret += data[x];
        }
        return ret;
    }

    T sum(int l, int r) const {
        return prefix_sum(r) - prefix_sum(l);
    }

    T all_sum() const {
        return prefix_sum(n);
    }

    // prefix_sum(x) >= key となる最小のxを返す関数 O(log N)

    int lower_bound(T key) {
        if (key <= 0) return 0;
        int x = 0;
        int max = 1;
        while ((max << 1) <= n) max <<= 1;
        for (int k = max; k > 0; k >>= 1) {
            if (x + k <= n && data[x + k] < key) {
                x += k;
                key -= data[x];
            }
        }
        return x + 1;
    }
};

}  // namespace ebi
#line 9 "data_structure/static_rectangle_sum.hpp"

namespace ebi {

template <class S, class T> struct static_rectangle_sum {
  private:
  public:
    static_rectangle_sum() = default;

    void add_point(S x, S y, T val) {
        p.emplace_back(x, y, val);
        cp_x.add(x);
        cp_y.add(y);
    }

    void add_query(S l, S d, S r, S u) {
        q.push_back({l, d, r, u});
        cp_x.add(l);
        cp_x.add(r);
        cp_y.add(d);
        cp_y.add(u);
    }

    std::vector<T> run() {
        assert(is_first);
        is_first = false;
        cp_x.build();
        cp_y.build();
        std::vector ptable(cp_x.size(), std::vector<int>());
        std::vector qtable(cp_x.size(), std::vector(2, std::vector<int>()));
        for (int i = 0; auto [x, y, val] : p) {
            ptable[cp_x.get(x)].emplace_back(i);
            i++;
        }
        for (int i = 0; auto [l, d, r, u] : q) {
            qtable[cp_x.get(l)][0].emplace_back(i);
            qtable[cp_x.get(r)][1].emplace_back(i);
            i++;
        }
        std::vector<T> res(q.size(), 0);
        fenwick_tree<T> ftree(cp_y.size());
        for (int i = 0; i < cp_x.size(); i++) {
            for (int j = 0; j < 2; j++) {
                for (auto idx : qtable[i][j]) {
                    int d = q[idx][1], u = q[idx][3];
                    res[idx] +=
                        (j == 0 ? -1 : 1) * ftree.sum(cp_y.get(d), cp_y.get(u));
                }
            }
            for (auto idx : ptable[i]) {
                auto [x, y, val] = p[idx];
                ftree.add(cp_y.get(y), val);
            }
        }
        return res;
    }

  private:
    bool is_first = true;
    std::vector<std::tuple<S, S, T>> p;
    std::vector<std::array<S, 4>> q;
    compress<S> cp_x, cp_y;
};

}  // namespace ebi

Back to top page