# Tree

## Abstract Data Type (ADT)

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~~

### Examples of ADT

* 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

#### References

* [TheAlgorithms/C-Plus-Plus](https://github.com/TheAlgorithms/C-Plus-Plus): medium quality C++ code, but comprehensive
* [Algorithm-DataStructures](https://github.com/jakobkogler/Algorithm-DataStructures): high quality C++ code (and a few in other languages) 
* Segment Tree
  * [C++ implementation](https://github.com/jakobkogler/Algorithm-DataStructures/blob/master/RangeQuery/SegmentTree.cpp)
  * [Tutorial in Chinese](https://blog.csdn.net/Yaokai_AssultMaster/article/details/79599809)
  * [Tutorial on CodeForces](https://codeforces.com/blog/entry/18051)

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

![](/files/-Mcc9pfJB-MgMFNXeAiM)

![](/files/-Mcc9y22UFhLdQvM4Tcm)

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wiki.hanzheteng.com/algorithm/cs/tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.