-
Notifications
You must be signed in to change notification settings - Fork 0
/
IntegerRangeFrequencyQueryTree.cpp
189 lines (189 loc) · 6.92 KB
/
IntegerRangeFrequencyQueryTree.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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
/*
* @title IntegerRangeFrequencyQueryTree - integer専用区間freq
* @docs md/needless/IntegerRangeFrequencyQueryTree.md
*/
template<unsigned int bit_length=20> class IntegerRangeFrequencyQueryTree {
using u64 = unsigned long long;
class SimpleBinaryTrie {
struct Node {
Node *left, *right;
u64 size;
Node(): size(0) {left=right=nullptr;}
};
Node* root;
size_t size(Node* node) const {return (node==nullptr ? 0 : node->size);}
bool empty(Node* node) const {return size(node) == 0;}
void print(Node* node,u64 i, u64 val) {
if(i == bit_length) {
cout << "{" << val << ":" << size(node) << ":" << size(node->left) << ":" << size(node->right) << "} ";
return;
}
if(node->left != nullptr) {
print(node->left, i+1, val);
}
if(node->right != nullptr) {
print(node->right, i+1, (val | (1UL<<(bit_length-1-i))) );
}
}
public:
SimpleBinaryTrie(): root(new Node()) {}
void insert(const u64 val) {
Node* curr = root; stack<Node*> st;
for(u64 i=0; i < bit_length; ++i) {
u64 j = ((val>>(bit_length-1-i)) & 1UL);
st.push(curr);
if(j) {
if(curr->right != nullptr) { curr = curr->right;}
else {
Node* next = new Node();
curr->right = next;
curr = next;
}
}
else {
if(curr->left != nullptr) curr = curr->left;
else {
Node* next = new Node();
curr->left = next;
curr = next;
}
}
}
curr->size += 1;
while(st.size()) {
auto node=st.top(); st.pop();
node->size = size(node->left) + size(node->right);
}
}
void erase(const u64 val) {
Node* curr = root; stack<Node*> st;
for(u64 i=0; i < bit_length; ++i) {
u64 j = ((val>>(bit_length-1-i)) & 1UL);
st.push(curr);
if(j) {
if(curr->right != nullptr) curr = curr->right;
else return;
}
else {
if(curr->left != nullptr) curr = curr->left;
else return;
}
}
if(empty(curr)) return;
curr->size -= 1;
while(st.size()) {
auto node=st.top(); st.pop();
node->size = size(node->left) + size(node->right);
}
}
size_t size() const {return size(root);}
bool empty() const {return empty(root);}
u64 kth_smallest(u64 k) const {
Node* curr = root; u64 val=0;
for(u64 i=0; i < bit_length; ++i) {
u64 j = 1UL << (bit_length-1-i);
u64 sz_l = size(curr->left);
if(k<sz_l) curr = curr->left;
else {
val |= j;
k -= sz_l;
curr = curr->right;
}
}
return val;
}
size_t lower_bound(const u64 val) const {
Node* curr = root;
u64 k=0;
for(u64 i=0; i < bit_length; ++i) {
u64 j = ((val>>(bit_length-1-i)) & 1UL);
if(j) {
k+=size(curr->left);
if(curr->right != nullptr) curr = curr->right;
else break;
}
else {
if(curr->left != nullptr) curr = curr->left;
else break;
}
}
return k;
}
size_t count(const u64 val) const {
Node* curr = root;
for(u64 i=0; i < bit_length; ++i) {
u64 j = ((val>>(bit_length-1-i)) & 1);
if(j) {
if(curr->right != nullptr) curr = curr->right;
else return 0;
}
else {
if(curr->left != nullptr) curr = curr->left;
else return 0;
}
}
return size(curr);
}
void print() {
cout << "{"; print(root,0,0); cout << "}" << endl;
}
};
size_t length;
size_t num;
vector<SimpleBinaryTrie> node;
void insert_impl(size_t idx, const u64 val) {
if(idx < 0 || length <= idx) return;
idx += length;
node[idx].insert(val);
while(idx >>= 1) node[idx].insert(val);
}
void erase_impl(size_t idx) {
if(idx < 0 || length <= idx) return;
idx += length;
if(node[idx].empty()) return;
u64 val = node[idx].kth_smallest(0);
node[idx].erase(val);
while(idx >>= 1) node[idx].erase(val);
}
int range_freq_upper_impl(int l, int r, const u64 upper) const {
if (l < 0 || length <= l || r < 0 || length < r) return 0;
int ret=0;
for(l += length, r += length; l < r; l >>=1, r >>=1) {
if(l&1) ret += node[l++].lower_bound(upper);
if(r&1) ret += node[--r].lower_bound(upper);
}
return ret;
}
int range_freq_impl(int l, int r, const u64 val) const {
if (l < 0 || length <= l || r < 0 || length < r) return 0;
int ret=0;
for(l += length, r += length; l < r; l >>=1, r >>=1) {
if(l&1) ret += node[l++].count(val);
if(r&1) ret += node[--r].count(val);
}
return ret;
}
public:
IntegerRangeFrequencyQueryTree(const u64 num) {
for (length = 1; length <= num; length *= 2);
node.resize(2 * length);
}
IntegerRangeFrequencyQueryTree(const vector<u64> & vec) {
for (length = 1; length <= vec.size(); length *= 2);
node.resize(2 * length);
for (int i=0; i < vec.size(); ++i) {
update(i, vec[i]);
}
}
//idx番目の要素をupdate
void update(const size_t idx, const u64 val) { erase_impl(idx); insert_impl(idx, val);}
//idx番目の要素をerase
void erase(const size_t idx) { erase_impl(idx); }
//[l,r) range freq of val (val < upper)
int range_freq_upper(const int l, const int r, const u64 upper) const {return range_freq_upper_impl(l,r,upper);}
//[l,r) range freq of val (lower <= val < upper)
int range_freq_lower_upper(const int l, const int r, const u64 lower, const u64 upper) const { return range_freq_upper_impl(l,r,upper) - range_freq_upper_impl(l,r,lower);}
//[l,r) range freq of val
int range_freq(const int l, const int r, const u64 val) const {return range_freq_impl(l,r,val);}
void print() { for(int i= length; i < 2*length; ++i) node[i].print();}
};