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

## Winning Tree

• An implementation of priority queue
• Easy to implement, same bound as binary heap
• Can also be used as a static version of search tree

#### Similar concepts

• 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)

#### Use case (as priority queue)

• Huffman coding: need `extract_min` and `insertion`
• Dijkstra's algorithm and Prim's algorithm: `extract_min` and `add/update`

### Implementation

• 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

### Augmented trees

• 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

## Example Code: Greedy & Winner Tree (code to be improved)

#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;
}