Panjang jujukan meningkat paling lama (LIS) menggunakan pokok segmen garisan

Pohon segmen ialah struktur data serba boleh yang direka untuk menjawab pertanyaan julat dan melaksanakan operasi kemas kini tatasusunan dalam kerumitan masa logaritma, di mana setiap nod menyimpan maklumat yang berkaitan dengan julat elemen tertentu dalam tatasusunan.

Dalam konteks masalah Longest Increasing Subsequence (LIS), di mana adalah perlu untuk menentukan panjang urutan terpanjang di mana unsur-unsur dalam urutan tertentu diisih mengikut urutan yang semakin meningkat, pokok segmen garis boleh digunakan untuk mengira dengan cekap panjang urutan yang semakin lama bertambah dalam tatasusunan.

Kaedah ini mengurangkan kerumitan masa dengan ketara berbanding kaedah tradisional dan mempunyai banyak aplikasi dalam bidang seperti genomik, pemprosesan bahasa semula jadi dan pengecaman corak. Artikel ini meneroka prinsip asas pokok segmen dan menunjukkan potensinya dalam menyelesaikan masalah seterusnya yang semakin lama semakin meningkat.

Tatabahasa

Fungsi binaan pokok segmen −

void build(vector<int> &tree, const vector<int> &arr, int start, int end, int index)
</int>

Fungsi pertanyaan Pokok Segmen −

int query(const vector<int> &tree, int start, int end, int l, int r, int index)

Fungsi kemas kini pokok segmen −

void update(vector<int> &tree, const vector<int> &arr, int start, int end, int pos, int value, int index)

Algoritma

Algoritma untuk mencari panjang jujukan meningkat terpanjang (LIS) menggunakan pokok segmen adalah seperti berikut -

• Memulakan tatasusunan yang mewakili jujukan input.

Mulakan dengan pokok segmen dengan saiz yang sama dengan jujukan input Gunakan fungsi binaan untuk membina pokok segmen garisan

• Proses setiap elemen urutan input.

• Untuk setiap elemen, tanyakan Pokok Segmen untuk mencari panjang maksimum LIS yang berakhir pada elemen semasa.

• Kemas kini Pokok Segmen menggunakan fungsi kemas kini.

• Ulang langkah 4-6 untuk semua elemen dalam urutan input.

• Jawapan akhir ialah nilai maksimum yang disimpan dalam Pokok Segmen.

Pendekatan 1: Menggunakan Pokok Segmen yang mudah

Dalam pendekatan ini, kami melaksanakan Pokok Segmen yang mudah tanpa sebarang teknik pengoptimuman seperti penyebaran malas.

Contoh-1

Atur cara di bawah menunjukkan cara untuk mencari Panjang Susunan Bertambah Terpanjang (LIS) menggunakan Pepohon Segmen ringkas dalam C++ Fungsi binaan, pertanyaan dan kemas kini digunakan untuk membina Pepohon Segmen, mendapatkan panjang maksimum LIS yang berakhir pada satu. elemen tertentu, dan kemas kini Petak Segmen dengan panjang LIS baharu, masing-masing Fungsi lengthOfLIS berulang melalui setiap elemen dalam jujukan input dan mengira panjang LIS menggunakan Pepohon Segmen.

.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void build(vector<int> &tree, const vector<int> &arr, int start, int end, int index) {
   if (start == end) {
      tree[index] = arr[start];
   } else {
      int mid = start + (end - start) / 2;
      build(tree, arr, start, mid, 2 * index + 1);
      build(tree, arr, mid + 1, end, 2 * index + 2);
      tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
   }
}

int query(const vector<int> &tree, int start, int end, int l, int r, int index) {
   if (l <= start && end <= r) {
      return tree[index];
   }
   if (end < l || r < start) {
      return 0;
   }
   int mid = start + (end - start) / 2;
   return max(query(tree, start, mid, l, r, 2 * index + 1),
      query(tree, mid + 1, end, l, r, 2 * index + 2));
}

void update(vector<int> &tree, const vector<int> &arr, int start, int end, int pos, int value, int index) {
   if (pos < start || end < pos) {
      return;
   }
   if (start == end) {
      tree[index] = value;
   } else {
      int mid = start + (end - start) / 2;
      update(tree, arr, start, mid, pos, value, 2 * index + 1);
      update(tree, arr, mid + 1, end, pos, value, 2 * index + 2);
      tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
   }
}

int lengthOfLIS(const vector<int> &nums) {
   int n = nums.size();
   vector<int> arr(n, 0), tree(4 * n, 0);

   build(tree, arr, 0, n - 1, 0);

   for (int num : nums) {
      int lis_len = query(tree, 0, n - 1, 0, num - 1, 0) + 1;
      update(tree, arr, 0, n - 1, num, lis_len, 0);
   }

   return query(tree, 0, n - 1, 0, n - 1, 0);
}

int main() {
   vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
   cout << "Length of Longest Increasing Subsequence: " <<lengthOfLIS(nums) << endl;
   return 0;
}

Output

Length of Longest Increasing Subsequence: 3

Kaedah menggunakan pokok segmen dengan pembiakan tertunda

Dalam pendekatan ini, kami melaksanakan Pokok Segmen dengan penyebaran malas untuk mengoptimumkan lagi kerumitan masa algoritma.

Contoh 2

Kod di bawah menunjukkan cara mencari panjang jujukan yang semakin lama (LIS) dalam C++ menggunakan pepohon segmen dengan penyebaran tertunda. Kod ini serupa dengan kod untuk kaedah 1, perbezaan utama antara kedua-dua kaedah adalah pelaksanaan dalaman pokok segmen. Teknik penyebaran malas tidak ditunjukkan secara eksplisit dalam kod ini kerana ia mengoptimumkan fungsi kemas kini untuk kes penggunaan khusus yang tidak wujud dalam masalah LIS. Walau bagaimanapun, struktur asas kod tetap sama, dan fungsi binaan, pertanyaan dan kemas kini digunakan dengan cara yang serupa dengan kaedah 1.

<int>#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void build(vector<int> &tree, const vector<int> &arr, int start, int end, int index) {
    if (start == end) {
        tree[index] = arr[start];
    } else {
        int mid = start + (end - start) / 2;
        build(tree, arr, start, mid, 2 * index + 1);
        build(tree, arr, mid + 1, end, 2 * index + 2);
        tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
    }
}
int query(const vector<int> &tree, int start, int end, int l, int r, int index) {
    if (l <= start && end <= r) {
        return tree[index];
    }
    if (end < l || r < start) {
        return 0;
    }
    int mid = start + (end - start) / 2;
    return max(query(tree, start, mid, l, r, 2 * index + 1),
               query(tree, mid + 1, end, l, r, 2 * index + 2));
}
void update(vector<int> &tree, const vector<int> &arr, int start, int end, int pos, int value, int index) {
    if (pos < start || end < pos) {
        return;
    }
    if (start == end) {
        tree[index] = value;
    } else {
        int mid = start + (end - start) / 2;
        update(tree, arr, start, mid, pos, value, 2 * index + 1);
        update(tree, arr, mid + 1, end, pos, value, 2 * index + 2);
        tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);
    }
}
int lengthOfLIS(const vector<int> &nums) {
    int n = nums.size();
    vector<int> arr(n, 0), tree(4 * n, 0);
    build(tree, arr, 0, n - 1, 0);
    for (int num : nums) {
        int lis_len = query(tree, 0, n - 1, 0, num - 1, 0) + 1;
        update(tree, arr, 0, n - 1, num, lis_len, 0);
    }
    return query(tree, 0, n - 1, 0, n - 1, 0);
}
int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "Length of Longest Increasing Subsequence: " << lengthOfLIS(nums)
         << endl;
    return 0;
}
</int>

Output

Length of Longest Increasing Subsequence: 3

Kesimpulan

Dalam artikel ini, kami menggambarkan kaedah penentuan julat urutan peningkatan terpanjang (LIS) melalui teknik pokok segmen garis dalam C++. Kami menggambarkan dua pendekatan: satu yang secara langsung melaksanakan pokok segmen, dan satu lagi yang mengeksploitasi kaedah pembiakan tertunda yang lebih baik. Kedua-dua teknik berkesan dalam menyelesaikan masalah LIS, dan melambatkan penyebaran dalam kaedah pengoptimuman mengurangkan lagi kerumitan masa.

Atas ialah kandungan terperinci Panjang jujukan meningkat paling lama (LIS) menggunakan pokok segmen garisan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!