Нахождение максимума в массиве за время O (log (n)) - с некоторыми допущениями

Question

я получил следующий вопрос: Предположим, у вас есть массив A с n отличительными номерами, и предположим, что вы можете хранить n-элементы в новой структуре данных (которая может помочь вам в решении вопроса ниже), сохраняя при этом, что время хранения ограничено O (n) , Напишите алгоритм для функции max (i, j), который получит в качестве входных данных два индекса i, превышающих j, и вернет в качестве выходных данных максимум между A [i], A [i + 1], ..., A [ J]. max (i, j) должно быть ограничено O (log (n)).

Я думал о двоичном дереве, но не мог понять, почему хранить числа. Один из вариантов, который я мог бы подумать о том, чтобы занять O (n) времени хранения, - это создание «дерева турниров», но мне не удалось найти алгоритм для максимального использования такой структуры данных.

Это вопрос домашнего задания, но не удалось найти для него тег.

Answer 1

Вы можете решить это, используя приоритетные очереди.

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;
}

Answer 2

Это наиболее типичное применение дерева сегментов .

Учитывая массив чисел, вы можете построить сегмент поверх него с O(n) сложностью по времени и выполнить запрос по интервалам / диапазонам за O(logn) по времени.

Некоторый типичный пример применения - поиск суммы элементов от индекса i до j, где 0 <= i <= j <= n - 1, нахождение максимума / минимума элементов от индекса i до j, где 0 <= i <= j <= n - 1 и т. Д.