-
Notifications
You must be signed in to change notification settings - Fork 2
/
Merge sort tree.cpp
59 lines (46 loc) · 1.24 KB
/
Merge sort tree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*8<{=======~ BEGIN MERGE SORT TREE ~=========>8*/
/*8<
@Title: Merge sort tree
@Description:
Like a segment tree but each node stores
the ordered subsegment it represents.
@Usage:
\begin{compactitem}
\item \textbf{$inrange(l, r, a, b)$} :
counts the number of positions $i$, $ l \leq
i \leq r$ such that $ a
\leq x_i \leq b$.
\end{compactitem}
@Time:
Build $O(N \log{N}^2)$, inrange $O(\log{N}^2)$
@Memory: $O(n \log{N})$
>8*/
template <class T>
struct MergeSortTree {
int n;
vector<vector<T>> st;
MergeSortTree(vector<T> &xs)
: n(len(xs)), st(n << 1) {
rep(i, 0, n) st[i + n] = vector<T>({xs[i]});
rrep(i, n - 1, 0) {
st[i].resize(len(st[i << 1]) +
len(st[i << 1 | 1]));
merge(all(st[i << 1]), all(st[i << 1 | 1]),
st[i].begin());
}
}
int count(int i, T a, T b) {
return upper_bound(all(st[i]), b) -
lower_bound(all(st[i]), a);
}
int inrange(int l, int r, T a, T b) {
int ans = 0;
for (l += n, r += n + 1; l < r;
l >>= 1, r >>= 1) {
if (l & 1) ans += count(l++, a, b);
if (r & 1) ans += count(--r, a, b);
}
return ans;
}
};
/*8<=========~ END MERGE SORT TREE ~=========}>8*/