this is for holding javascript data
Xavier Holt edited Max_Population_Cities_Wrong_Needs__.md
about 8 years ago
Commit id: 3911bd9d682b18d681f47d9bf615815d22a1a663
deletions | additions
diff --git a/Max_Population_Cities_Wrong_Needs__.md b/Max_Population_Cities_Wrong_Needs__.md
index fdc18d0..97d1ced 100644
--- a/Max_Population_Cities_Wrong_Needs__.md
+++ b/Max_Population_Cities_Wrong_Needs__.md
...
# Max Population Cities
**Wrong Needs Fixing**
## Preprocessing
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
among all nodes in
their subtrees. the subtree rooted at this node.
We can achieve this while maintaining overall runtime if we build Building our auxiliary
data-structures from leaf-node up (**Figure 1**). Starting from the leafs, we perform data-structure takes \(O(n)\) work, where \(n\) is the
merging step number of
merge-sort on nodes stored in that sub-tree. We can store the
y-coordinates of our pointset. Every merge-step corresponds to maximum population for all nodes in the auxiliary
data-structure for a node graph in
our \(x\)-tree. a linear amount of time.
The only additional thing we have to We do
is keep track of this with a simple in-order traversal (recursively, the
maximum population city. In left and right subtrees are visited before the
first layer of merging root). When we
are comparing two leaves. We can reach an internal node, we just compare
the population sizes
of the two children and store the
maximum in larger of the two. Our traversal is \(O(n)\) and we do \(O(1)\)
extra work
per merge. For all sequential layers, we simply compare at each node so the
two population sizes and store total run-time is \(O(n)\). As such we have not altered the
largest value. big-oh complexity of building our auxiliary data-structure.
## Queries
We query
in mostly the
same way as general range trees. We first search our \(x\)-tree and then find \(O(\log n)\) auxiliary data-structures. In each of these, we find the \(O(\log n)\) sub-trees determining our valid \(y-\)-range. Instead of traversing this segment of the graph, we simply look at the population sizes stored in the root of the subtrees. We find the maximum such value for each auxiliary tree, and then compare these to find the overall maximum value.
- For each auxiliary tree i: \(O(\log n)\)
- Find the sub-trees determining the valid \(y\)-range: \(O(\log n)\)
- \(m_i\rightarrow\) the maximum root-value among all sub-trees: There are \(O(\log n)\) such sub-trees so this is \(O(\log n)\).
- Emit \(\max(m_j)\): There are \(O(\log n)\) auxiliary trees so this is \(O(\log n)\).
## Complexity
**Preprocessing:** The process of building the auxiliary tree is
a merge-step with \(O(1)\) additional work \(O(n)\) per
merge. layer with \(\log n\) layers. As such, it runs in \(O(n\log n\) time. This is additive to the \(O(n\log n\) time required to build the \(x\)-tree, so we have overall \(O(n\log n\) pre-processing time.
**Space:** We also maintain the \(O (n\log n)\) space bound of range-trees -- we
are storing store only one additional value per
layer in the auxiliary data-structure.
**Query Time:**
To find the valid region we perform \(O(\log n\)\) look-ups in \(O(\log n\)\) auxiliary trees.