Finding maximum in array in time of O(log(n))- with some assumptions

I got the following question:
Assume you got an array A with n distinguished numbers, and assume you can store the n-elements in new data structure (one that could help you in solving the question below) while saving the that the store time is bounded by O(n).
Write an algorithm for a function max (i,j) which will get as input two index i greater then j , and will return as output the maximum between A[i], A[i+1],...,A[j]. max(i,j) should be bounded by O(log(n)).

I thought about binary tree but could not think about a why of how to store the numbers. One option that I could thought about that take O(n) store time is creating a 'tournament tree' , but I failed to find an algorithm to max using this kind of data structure.

This is a homework question, but couldn't find the tag for it.

2 Answers
2

This is the most typical application of segment tree.

Given an array of number, you can build a segment on top of it with O(n) time complexity and perform query on intervals/ranges in O(logn) time.

O(n)

O(logn)

Some common application example - finding the sum of elements from index i to j where 0 <= i <= j <= n - 1, finding the maximum/minimum of elements from index i to j where 0 <= i <= j <= n - 1 etc.

i

j

0 <= i <= j <= n - 1

i

j

0 <= i <= j <= n - 1

You can solve it using priority queues.

using namespace std;
#include<iostream>
#include<vector>
#include<algorithm>
int deq[100],length=0;
void increase_value(int arr,int i,int val)

arr[i]=val;
while(i>1 && arr[i/2]<arr[i])

int temp=arr[i];
arr[i]=arr[i/2];
arr[i/2]=temp;
i=i/2;


void insert_element(int arr,int val)

length=length+1;
increase_value(arr,length,val);

int main()

int arr[10000];
int size,lw,up;
cin>>size;
for(int i=1;i<=size;i++)

cin>>arr[i];

cin>>lw>>up;
for(int i=lw;i<=up;i++)

insert_element(deq,arr[i]);

cout<<deq[1]<<endl;



insert_element

lw

up

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.