Merge Segtree
コードについての説明
長方形領域に対する静的クエリに効率良く答えるデータ構造. 以下の実装では二次元座標上の各点が値と対応しているときに, 長方形領域内に含まれる点に対応する値の和を求めるデータ構造になっている.
二次元座標上の点集合を扱う際に, まず座標を $x$ 座標について昇順に並べてセグ木を構築するのだが, このときセグ木の各ノードにそのノードの範囲 $x \in [l, r)$ に含まれる頂点集合を今度は $y$ 座標について昇順になるように配列で保持しておく.
このように並べておくことで長方形領域についての静的クエリがきたときに $x$ 座標の範囲に対応する $\O (\log n)$ 個のセグ木のノードを見て, それぞれについて $y$ 座標の範囲のクエリを処理する(各ノードでは点が $y$ 座標について昇順になるように並べられているので範囲クエリに $\O (\log n)$ time で答えることができる).
領域木 の場合は各ノードに対応する頂点集合を配列ではなく新たなセグ木で管理する. そのため領域木の特殊版ともいえる.
フラクショナルカスケーディングと呼ばれる技法を用いることで二分探索を各ノードではなく初めに 1 回のみ行うように変更することができ、結果的に $\O (\log n)$ の計算量で解くことが可能になる.
しかし以下の実装では理論計算量の意味では遅い $\O (\log^2 n)$ の場合の方が速く動作した.
時間計算量: 構築 $\O (n \log n)$, 各クエリ $\O (\log^2 n)$ (フラクショナルカスケーディング版は $\O (\log n)$)
空間計算量: 構築 $\O (n \log n)$
コード
#define all(v) (v).begin(),(v).end()
template<typename CandidateType, typename ValueType> class segtree
{
private:
using CT = CandidateType;
using VT = ValueType;
using pcc = pair<CT, CT>;
using pci = pair<CT, int>;
int n, sz;
// x座標
vector<CT> xs;
// y座標
vector<vector<CT> > ys;
// 累積和
vector<vector<VT> > sum;
VT _query(int a, int b, const CT ly, const CT ry){
VT res1 = 0, res2 = 0;
a += n, b += n;
while(a != b){
if(a & 1){
const int c = lower_bound(all(ys[a]), ly) - ys[a].begin();
const int d = lower_bound(all(ys[a]), ry) - ys[a].begin();
res1 += sum[a][d] - sum[a][c];
++a;
}
if(b & 1){
--b;
const int c = lower_bound(all(ys[b]), ly) - ys[b].begin();
const int d = lower_bound(all(ys[b]), ry) - ys[b].begin();
res2 += sum[b][d] - sum[b][c];
}
a >>= 1, b >>= 1;
}
return res1 + res2;
}
public:
segtree(const vector<pcc>& cand, const vector<VT>& val) : n(1), sz((int)cand.size()), xs(sz){
while(n < sz) n *= 2;
vector<vector<pci> > hoge(2*n);
vector<pci> sorted(sz);
for(int i = 0; i < sz; ++i) sorted[i] = {cand[i].first, i};
sort(all(sorted));
ys.resize(2*n), sum.resize(2*n);
for(int i = 0; i < sz; ++i){
xs[i] = sorted[i].first, ys[i+n] = {cand[sorted[i].second].second};
hoge[i+n] = {pci(cand[sorted[i].second].second, sorted[i].second)};
sum[i+n] = {0, val[sorted[i].second]};
}
for(int i = n - 1; i >= 1; --i){
hoge[i].resize((int)hoge[2*i].size() + (int)hoge[2*i+1].size());
merge(all(hoge[2*i]), all(hoge[2*i+1]), hoge[i].begin(), [&](pci& a, pci& b){
return a.first < b.first;
});
ys[i].resize((int)hoge[i].size()), sum[i].resize((int)hoge[i].size() + 1, 0);
for(int j = 0; j < (int)hoge[i].size(); ++j){
ys[i][j] = hoge[i][j].first, sum[i][j+1] = sum[i][j] + val[hoge[i][j].second];
}
}
}
//[lx,rx)×[ly,ry)の長方形領域に含まれる値の和に答える
VT query(const CT lx, const CT ly, const CT rx, const CT ry){
const int lxid = lower_bound(all(xs), lx) - xs.begin();
const int rxid = upper_bound(all(xs), rx-1) - xs.begin();
if(lxid >= rxid) return 0;
return _query(lxid, rxid, ly, ry);
}
};
コード(フラクショナルカスケーディング版)
template<typename CandidateType, typename ValueType> class segtree
{
private:
using CT = CandidateType;
using VT = ValueType;
struct info {
int left, right;
VT sum;
info(const int _left, const int _right, const VT _sum)
: left(_left), right(_right), sum(_sum){}
};
int m;
vector<CT> xs, ys;
vector<info> ptr;
vector<int> st;
int update(const int prv, const int xid, const VT val, const int l, const int r){
const int cur = (int)ptr.size();
ptr.emplace_back(0, 0, ptr[prv].sum + val);
if(r - l == 1) return cur;
const int mid = (l + r) / 2;
if(xid < mid){
const int res = update(ptr[prv].left, xid, val, l, mid);
ptr[cur].left = res, ptr[cur].right = ptr[prv].right;
}else{
const int res = update(ptr[prv].right, xid, val, mid, r);
ptr[cur].left = ptr[prv].left, ptr[cur].right = res;
}
ptr[cur].sum = ptr[ptr[cur].left].sum + ptr[ptr[cur].right].sum;
return cur;
}
void preprocessing(const vector<pair<CT, CT> >& cand, const vector<VT>& val){
const int n = (int)cand.size();
vector<pair<CT, int> > sorted(n);
for(int i = 0; i < n; ++i){
xs[i] = cand[i].first, sorted[i] = {cand[i].second, i};
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
sort(sorted.begin(), sorted.end());
m = (int)xs.size();
int prv = 0;
st.push_back(prv), ptr.emplace_back(0, 0, 0);
for(const auto& p : sorted){
const int newx = (int)(lower_bound(xs.begin(), xs.end(), cand[p.second].first) - xs.begin());
prv = update(prv, newx, val[p.second], 0, m);
if(ys.empty() || ys.back() < p.first) st.push_back(prv), ys.push_back(p.first);
else st.back() = prv;
}
}
VT query(const int cur, const int a, const int b, const int l, const int r){
if(cur == 0 || b <= l || r <= a) return 0;
if(a <= l && r <= b) return ptr[cur].sum;
const int mid = (l + r) / 2;
return query(ptr[cur].left, a, min(b, mid), l, mid) + query(ptr[cur].right, max(a, mid), b, mid, r);
}
public:
segtree(const vector<pair<CT, CT> >& cand, const vector<VT>& val) : xs((int)cand.size()){
preprocessing(cand, val);
}
//[lx,rx)×[ly,ry)の長方形領域に含まれる値の和に答える
VT query(const CT lx, const CT ly, const CT rx, const CT ry){
const int lxid = lower_bound(xs.begin(), xs.end(), lx) - xs.begin();
const int rxid = lower_bound(xs.begin(), xs.end(), rx) - xs.begin();
const int lyid = lower_bound(ys.begin(), ys.end(), ly) - ys.begin();
const int ryid = lower_bound(ys.begin(), ys.end(), ry) - ys.begin();
if(lxid == rxid || lyid == ryid) return 0;
else return query(st[ryid], lxid, rxid, 0, m) - query(st[lyid], lxid, rxid, 0, m);
}
};
verify 用の問題
Atcoder : League of Kyoto
提出コード
yosupo さんの libary checker : Rectangle Sum
提出コード
提出コード(フラクショナルカスケーディング版)