this is for holding javascript data
Xavier Holt edited Max_Population_Cities_Preprocessing_We__.md
about 8 years ago
Commit id: eed7965e6e491bad183aaa31855dff9a9e58312e
deletions | additions
diff --git a/Max_Population_Cities_Preprocessing_We__.md b/Max_Population_Cities_Preprocessing_We__.md
index 0f872dd..24d53c8 100644
--- a/Max_Population_Cities_Preprocessing_We__.md
+++ b/Max_Population_Cities_Preprocessing_We__.md
...
We store the tuple of coordinates in a range-tree. The auxiliary data structure at each node also keeps track of the maximum population city in the subtree rooted at this node.
Building our auxiliary
data-structure takes data-structures for general range-trees take \(O(n)\)
work, where \(n\) is the number of nodes stored in that sub-tree. work per layer. We can store the
maximum population for all nodes maximum-population data in
all subtrees with \(O(n)\) additional work per layer, maintaining the
auxiliary graph in a linear amount of overall preprocessing time.
We After we have the auxiliary tree, we do this with a simple in-order
traversal (recursively, the left and right subtrees are visited before the root). traversal. When we reach an internal node, we just compare the population sizes of the two children and store the larger of the two. Our traversal is \(O(n)\) and we do \(O(1)\) work at each node so the total run-time is \(O(n)\).
As such we have not altered the big-oh complexity of building our auxiliary data-structure.
## Queries