Comment on page
Tree
A mathematical model for data types:
- How to store data
- What query to support? (lookup, findMin, findSum, …)
- What update to support? (insertion, deletion, filter, multi_insert, delete_min, …)
- Algorithms for the operations
- FIFO Queue
- Deque (double-ended queue)
- Stack
- Priority queue
- Ordered set/map
- Unordered set/map
- An implementation of priority queue
- Easy to implement, same bound as binary heap
- Can also be used as a static version of search tree
- Also Winner Tree, Tournament Tree
- Segment Tree (w/o insert, delete operations).
- Fenwick tree or binary indexed tree (only used to efficiently calculate prefix sums)
- Huffman coding: need
extract_minandinsertion - Dijkstra's algorithm and Prim's algorithm:
extract_minandadd/update
- store all elements at the leaves (N nodes)
- each internal node is a competition (N-1 nodes)
- insertion, deletion, update operations at O(log n) time; the bound is tight
- can also use an array to store it
- two children of A[i]: A[2i] and A[2i+1] (start from 1 can make it easier, but can also start from 0)
- a complete binary tree
- a good alternative to binary heap
- same asymptotical bound for insertion/deletion/update/extract_min
- easy to implement
- takes more space, and is slightly slower in practice
- when combining with augmentation, can be used to implement almost all data structures
- Segment Tree
- Range-related queries: 1D range max/min/sum
- Extract-Min is a special range query (on the entire range)
- We can augment the winning tree according to designated tasks
- store different field for different query
- often augment multiple fields at the same time
- If we pre-sort all elements or the key range is fixed (e.g., entire range)
- winning tree can be used as a static search tree
- For floating-point range query, we can discretize it and map it to integers
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <functional>
struct node {
int key_min;
int key_max;
int value_min;
int value_max;
int idx;
};
// winner tree implementation
// faster, passed 8/10 cases
// the way to remove/update "used" nodes can be faster?
int main(){
int n, m;
std::cin >> n >> m;
std::vector<int> instructor(n);
for (int i = 0; i < n; ++i)
scanf("%d", &instructor[i]);
std::sort(instructor.begin(), instructor.end());
// construct (static) winner tree
std::vector<node> tree(2*m);
for (int i = m; i < 2*m; ++i) {
scanf("%d %d", &tree[i].key_max, &tree[i].value_min); // key, value --> student start day, end day
tree[i].idx = i;
tree[i].key_min = tree[i].key_max;
tree[i].value_max = tree[i].value_min;
}
for (int i = m-1; i > 0; --i) { // leave idx 0 unused
tree[i].key_min = std::min(tree[2*i].key_min, tree[2*i+1].key_min); // save min key
tree[i].key_max = std::max(tree[2*i].key_max, tree[2*i+1].key_max); // save max key
tree[i].value_min = std::min(tree[2*i].value_min, tree[2*i+1].value_min); // save min value
tree[i].value_max = std::max(tree[2*i].value_max, tree[2*i+1].value_max); // save max value
tree[i].idx = tree[2*i].value_min < tree[2*i+1].value_min ? tree[2*i].idx : tree[2*i+1].idx; // save min value idx
}
// this recursive function is the critical part
std::function<void(int,int,int,int&,int&)> range_min = [&tree, &range_min, &m](int i, int key_right, int value_left, int& min_value, int& idx){
if (i >= 2*m) return;
if (tree[i].key_min > key_right || tree[i].value_max < value_left) return;
if (tree[i].key_max <= key_right && value_left <= tree[i].value_min){
if(min_value > tree[i].value_min){
min_value = tree[i].value_min;
idx = tree[i].idx;
}
return;
}
range_min(i*2, key_right, value_left, min_value, idx);
range_min(i*2+1, key_right, value_left, min_value, idx);
};
auto tree_update = [&tree](int i, int new_value){
tree[i].value_min = new_value;
tree[i].value_max = new_value;
while (i > 1){
i = i / 2;
tree[i].value_min = std::min(tree[2*i].value_min, tree[2*i+1].value_min); // save min value
tree[i].value_max = std::max(tree[2*i].value_max, tree[2*i+1].value_max); // save max value
tree[i].idx = tree[2*i].value_min < tree[2*i+1].value_min ? tree[2*i].idx : tree[2*i+1].idx; // save min value idx
}
};
int max_num_students = 0;
for (auto& ins_day : instructor) { // O(n)
int earliest_stu_end_day = std::numeric_limits<int>::max();
int earliest_idx = -1;
range_min(1, ins_day, ins_day, earliest_stu_end_day, earliest_idx); // O(log(m))
if (earliest_idx == -1) continue;
tree_update(earliest_idx, std::numeric_limits<int>::max()); // O(log(m))
max_num_students++;
}
std::cout << max_num_students << std::endl;
return 0;
}
Last modified 2yr ago