MATH208 Project 6- Segment Tree Solution

1 Description of Assignment
Let m and n be two large integers. Given an array of n integers x1,x2,...,xn. Design and implement efficient data structure and algorithms for a set of m queries.
Each query takes input lj and rj and output max {xi}, for j = 1,2,...,m.
lj≤i≤rj
On the other hand, a table A of n × n can be constructed so that A[l,r] contains max{xi}. By using table A, each query can be answered in O(1) time. However, l≤i≤r computing table A needs O(n2) time and the table takes O(n2) spaces.
There are two tasks in this assignment. First design a data structure with size O(n) and an algorithm to construct the data structure in linear time. Then, design an O(logn) time algorithm to process each query using the data structure.
2 Input
The first part of the input is n and x1,x2,...,xn. The second part of the input is the m queries. Each query is specified by lj and rj, j = 1,2,...,m. Both parts of input data, except m and n, can be generated randomly.
3 Output
For each query lj and rj print out the value of the maximum element mj in {xlj,xlj+1,...,xrj}.
Compare the performance of your program with the straightforward method. The straightforward method should also be used to verify whether the answer of your program is correct or not.
Notes
The format of the report of the assignment does not need to be very formal, but it should be close to the format of a research technical report.
1
1. Title and author.
Include assignment number, your name, student number and email address on the first page of your report.
2. Statement of the problem.
A “formal” description of the problem in this assignment. In addition to the basic requirements specified in the assignment, emphasize the functions or features you implemented.
3. Main results.
This section should include at least the following items.
(a) Description of the design of your program and the data structures used in your program.
(b) List of your program with comments. If your program is very long, list only the main parts of the program here and the entire program in an appendix. Additional comments can be added manually to explain the design of the program.
(c) Outputs of the compilation and the executions of your program.
4. Conclusions
Give a brief summary of what you did, and interesting thing you learned from this assignment.
Additional notes:
2. The output of the program execution should indicate the correctness of your program. In other words, a set of comprehensive (but not necessarily exhaustive) annotated test data for the problem should be provided to show that your program is indeed correct. This can be done by carefully selecting a set of test data.
3. Print or write the report on A4 papers. Bind them together in the upper left corner.
2