Difference between revisions of "TADM2E 3.11"
(Recovering wiki) |
|||
| Line 1: | Line 1: | ||
| − | + | ==== 1. Design a data structure that uses <math>O(n^2)</math> space and answers queries in <math>O(1)</math> time. ==== | |
| − | + | ||
| − | + | Build an <math>n × n</math> lookup table with the answer to every possible query, indexed by <math>i</math> and <math>j</math>. | |
| − | + | ||
| + | ==== 2. Design a data structure that uses <math>O(n)</math> space and answers queries in <math>O(\log n)</math> time. ==== | ||
| + | |||
| + | The basic idea in this solution is to build a multi-resolution representation of the input, with each node able to answer the query for part of the input sequence. A tree of such nodes makes it possible to answer arbitrary queries quickly by covering the query range with ranges covered by nodes. | ||
| + | |||
| + | Build a binary tree in which each node holds the lowest value for a range of indexes. The root node spans the whole input sequence. The root node's children span the left and right halves of the input sequence, and so on. Each leaf node spans a single-element "range" of the input, with the "lowest" value in that range being the value at that position in the input sequence. The total number of nodes in the tree is <math>O(n)</math>. | ||
| + | |||
| + | The query function is recursive, starting from the root: | ||
| + | |||
| + | * If the query range exactly matches the range spanned by the current node, return the current node's value. | ||
| + | * If the query range falls entirely within the left half, return the result of calling the query function on the left child. | ||
| + | * If the query range falls entirely within the right half, return the result of calling the query function on the right child. | ||
| + | * Otherwise return the lowest of the results from calling the query function on the left child and the right child. | ||
| + | |||
| + | The query function will visit at most two leaf nodes, and runs in <math>O(\log n)</math> time. | ||
Revision as of 22:53, 7 January 2015
1. Design a data structure that uses $ O(n^2) $ space and answers queries in $ O(1) $ time.
Build an $ n × n $ lookup table with the answer to every possible query, indexed by $ i $ and $ j $.
2. Design a data structure that uses $ O(n) $ space and answers queries in $ O(\log n) $ time.
The basic idea in this solution is to build a multi-resolution representation of the input, with each node able to answer the query for part of the input sequence. A tree of such nodes makes it possible to answer arbitrary queries quickly by covering the query range with ranges covered by nodes.
Build a binary tree in which each node holds the lowest value for a range of indexes. The root node spans the whole input sequence. The root node's children span the left and right halves of the input sequence, and so on. Each leaf node spans a single-element "range" of the input, with the "lowest" value in that range being the value at that position in the input sequence. The total number of nodes in the tree is $ O(n) $.
The query function is recursive, starting from the root:
- If the query range exactly matches the range spanned by the current node, return the current node's value.
- If the query range falls entirely within the left half, return the result of calling the query function on the left child.
- If the query range falls entirely within the right half, return the result of calling the query function on the right child.
- Otherwise return the lowest of the results from calling the query function on the left child and the right child.
The query function will visit at most two leaf nodes, and runs in $ O(\log n) $ time.
