Mengambil nilai maksimum dari rentang dalam array yang tidak disortir

Saya memiliki array yang tidak disortir . Saya memiliki pertanyaan di mana saya memberikan rentang dan kemudian nilai maksimum dari rentang itu harus dikembalikan. Sebagai contoh:

array[]={23,17,9,45,78,2,4,6,90,1};
query(both inclusive): 2 6
answer: 78

Algoritme atau struktur data mana yang saya buat untuk dengan cepat mengambil nilai maksimum dari rentang apa pun. (Ada banyak pertanyaan)

EDIT: Ini memang versi sederhana dari masalah aktual. Saya dapat memiliki ukuran array sebesar 100000 dan jumlah permintaan hingga 100000. Jadi saya pasti memerlukan beberapa preprocessing yang akan memfasilitasi respon permintaan yang cepat.

Saya pikir Anda bisa membangun semacam pohon biner di mana setiap node mewakili nilai maksimum anak-anaknya:

            78           
     45            78     
  23    45     78      6  
23 17  9 45   78 2    4 6   

Maka Anda hanya perlu menemukan cara untuk menentukan node mana yang paling tidak perlu Anda periksa untuk menemukan nilai maksimum dalam rentang yang ditanyakan. Dalam contoh ini, untuk mendapatkan nilai maksimum dalam rentang indeks [2, 6](inklusif) yang Anda miliki max(45, 78, 4)sebagai gantinya max(9, 45, 78, 2, 4). Saat pohon tumbuh, keuntungannya akan lebih besar.

Untuk melengkapi jawaban ngoaho91.

Cara terbaik untuk mengatasi masalah ini adalah menggunakan struktur data Segment Tree. Ini memungkinkan Anda untuk menjawab pertanyaan seperti di O (log (n)), itu berarti kompleksitas total algoritma Anda akan menjadi O (Q logn) di mana Q adalah jumlah permintaan. Jika Anda menggunakan algoritma naif, kompleksitas totalnya adalah O (Q n) yang jelas lebih lambat.

Namun, ada kelemahan dari penggunaan Pohon Segmen. Membutuhkan banyak memori, tetapi seringkali Anda tidak terlalu peduli dengan memori daripada kecepatan.

Saya akan menjelaskan secara singkat algoritma yang digunakan oleh DS ini:

Pohon segmen hanya kasus khusus dari Pohon Pencarian Biner, di mana setiap node memegang nilai rentang itu ditugaskan. Simpul root, diberikan kisaran [0, n]. Anak kiri diberi kisaran [0, (0 + n) / 2] dan anak kanan [(0 + n) / 2 + 1, n]. Dengan cara ini pohon akan dibangun.

Buat Pohon :

/*
    A[] -> array of original values
    tree[] -> Segment Tree Data Structure.
    node -> the node we are actually in: remember left child is 2*node, right child is 2*node+1
    a, b -> The limits of the actual array. This is used because we are dealing
                with a recursive function.
*/

int tree[SIZE];

void build_tree(vector<int> A, int node, int a, int b) {
    if (a == b) { // We get to a simple element
        tree[node] = A[a]; // This node stores the only value
    }
    else {
        int leftChild, rightChild, middle;
        leftChild = 2*node;
        rightChild = 2*node+1; // Or leftChild+1
        middle = (a+b) / 2;
        build_tree(A, leftChild, a, middle); // Recursively build the tree in the left child
        build_tree(A, rightChild, middle+1, b); // Recursively build the tree in the right child

        tree[node] = max(tree[leftChild], tree[rightChild]); // The Value of the actual node, 
                                                            //is the max of both of the children.
    }
}

Pohon Permintaan

int query(int node, int a, int b, int p, int q) {
    if (b < p || a > q) // The actual range is outside this range
        return -INF; // Return a negative big number. Can you figure out why?
    else if (p >= a && b >= q) // Query inside the range
        return tree[node];
    int l, r, m;
    l = 2*node;
    r = l+1;
    m = (a+b) / 2;
    return max(query(l, a, m, p, q), query(r, m+1, b, p, q)); // Return the max of querying both children.
}

Jika Anda perlu penjelasan lebih lanjut, beri tahu saya.

BTW, Segment Tree juga mendukung pembaruan elemen tunggal atau serangkaian elemen di O (log n)

Algoritma terbaik adalah dalam waktu O (n) seperti di bawah ini mari kita mulai, akhir menjadi indeks batas jangkauan

int findMax(int[] a, start, end) {
   max = Integer.MIN; // initialize to minimum Integer

   for(int i=start; i <= end; i++) 
      if ( a[i] > max )
         max = a[i];

   return max; 
}

Solusi berbasis pohon biner / segmen pohon memang menunjuk ke arah yang benar. Orang mungkin keberatan bahwa mereka membutuhkan banyak memori tambahan. Ada dua solusi untuk masalah ini:

1. Gunakan struktur data implisit alih-alih pohon biner
2. Gunakan pohon M-ary alih-alih pohon biner

Poin pertama adalah bahwa karena pohon sangat terstruktur, Anda dapat menggunakan struktur seperti tumpukan untuk secara implisit mendefinisikan pohon daripada mewakili pohon dengan node, pointer kiri dan kanan, interval dll. Itu menghemat banyak memori dengan dasarnya tidak ada hit kinerja - Anda perlu melakukan aritmatika pointer sedikit lebih.

Poin kedua adalah bahwa, dengan biaya sedikit lebih banyak pekerjaan selama evaluasi, Anda dapat menggunakan pohon M-ary daripada pohon biner. Misalnya jika Anda menggunakan pohon 3-ary Anda akan menghitung maks 3 elemen sekaligus, lalu 9 elemen sekaligus, kemudian 27, dll. Penyimpanan tambahan yang diperlukan adalah N / (M-1) - Anda dapat buktikan menggunakan rumus deret geometri. Jika Anda memilih M = 11, misalnya, Anda akan membutuhkan 1/10 penyimpanan metode pohon biner.

Anda dapat memverifikasi bahwa implementasi naif dan dioptimalkan ini di Python memberikan hasil yang sama:

class RangeQuerier(object):
    #The naive way
    def __init__(self):
        pass

    def set_array(self,arr):
        #Set, and preprocess
        self.arr = arr

    def query(self,l,r):
        try:
            return max(self.arr[l:r])
        except ValueError:
            return None

vs.

class RangeQuerierMultiLevel(object):
    def __init__(self):
        self.arrs = []
        self.sub_factor = 3
        self.len_ = 0

    def set_array(self,arr):
        #Set, and preprocess
        tgt = arr
        self.len_ = len(tgt)
        self.arrs.append(arr)
        while len(tgt) > 1:
            tgt = self.maxify_one_array(tgt)
            self.arrs.append(tgt)

    def maxify_one_array(self,arr):
        sub_arr = []
        themax = float('-inf')
        for i,el in enumerate(arr):
            themax = max(el,themax)
            if i % self.sub_factor == self.sub_factor - 1:
                sub_arr.append(themax)
                themax = float('-inf')
        return sub_arr

    def query(self,l,r,level=None):
        if level is None:
            level = len(self.arrs)-1

        if r <= l:
            return None

        int_size = self.sub_factor ** level 

        lhs,mid,rhs = (float('-inf'),float('-inf'),float('-inf'))

        #Check if there's an imperfect match on the left hand side
        if l % int_size != 0:
            lnew = int(ceil(l/float(int_size)))*int_size
            lhs = self.query(l,min(lnew,r),level-1)
            l = lnew
        #Check if there's an imperfect match on the right hand side
        if r % int_size != 0:
            rnew = int(floor(r/float(int_size)))*int_size
            rhs = self.query(max(rnew,l),r,level-1)
            r = rnew

        if r > l:
            #Handle the middle elements
            mid = max(self.arrs[level][l/int_size:r/int_size])
        return max(max(lhs,mid),rhs)

coba "segmen pohon" struktur data
ada 2 langkah
build_tree () O (n)
permintaan (int min, int max) O (nlogn)

http://en.wikipedia.org/wiki/Segment_tree

edit:

kalian tidak membaca wiki yang saya kirim!

algoritma ini adalah:
- Anda melintasi array 1 kali untuk membangun pohon. O (n)
- 10.000.000 berikutnya + kali Anda ingin tahu maks dari setiap bagian dari array, panggil saja fungsi permintaan. O (logn) untuk setiap kueri
- c ++ implementasikan di sini geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
algoritma lama adalah:
setiap kueri, cukup lintasi area yang dipilih dan temukan.

jadi, jika Anda akan menggunakan algoritma ini untuk memproses sekali, OK, itu lebih lambat daripada cara lama. tetapi jika Anda akan memproses sejumlah besar query (miliar), itu sangat efisien Anda dapat menghasilkan file teks seperti ini, untuk uji

baris 1: 50.000 nomor acak 0-1.000.000, split oleh '(space)' (itu array)
baris 2: 2 angka acak dari 1 hingga 50.000, dibagi dengan '(spasi)' (ini permintaan)
...
baris 200000: suka baris 2, itu juga kueri acak

ini adalah contoh masalah, maaf tapi ini dalam bahasa Vietnam
http://vn.spoj.com/problems/NKLINEUP/
jika Anda menyelesaikannya dengan cara lama, Anda tidak akan pernah lulus.

Anda dapat mencapai O (1) per kueri (dengan O (n log n) konstruksi) menggunakan struktur data yang disebut tabel jarang. Untuk setiap kekuatan 2 mari kita simpan maksimum untuk setiap segmen sepanjang ini. Sekarang diberikan segmen [l, r) Anda mendapatkan maksimum maksimum pada [l + 2 ^ k) dan [r-2 ^ k, r) untuk k yang sesuai. Mereka tumpang tindih tapi tidak apa-apa