使用線段樹求解最長遞增子序列 (LIS) 的長度

---

線段樹是一種通用的資料結構，用於在對數時間複雜度內回答範圍查詢並在陣列上執行更新操作，其中每個節點儲存與陣列中特定元素範圍相關的資訊。

線上段樹解決最長遞增子序列 (LIS) 問題（需要確定給定序列中最長子序列的長度，其中元素按遞增順序排序）的背景下，線段樹可以用來高效地計算陣列中 LIS 的長度。

與傳統方法相比，這種方法顯著降低了時間複雜度，並在基因組學、自然語言處理和模式識別等領域具有眾多應用。本文探討了線段樹的基礎知識，並演示了其在解決 LIS 問題方面的潛力。

語法

線段樹構建函式：

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

線段樹查詢函式：

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

線段樹更新函式：

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

演算法

使用線段樹查詢最長遞增子序列 (LIS) 長度的演算法如下：

• 初始化一個表示輸入序列的陣列。

• 初始化一個與輸入序列大小相同的線段樹。

• 使用構建函式構建線段樹。

• 處理輸入序列的每個元素。

• 對於每個元素，查詢線段樹以查詢以當前元素結尾的 LIS 的最大長度。

• 使用更新函式更新線段樹。

• 對輸入序列中的所有元素重複步驟 4-6。

• 最終答案是線段樹中儲存的最大值。

方法 1：使用簡單的線段樹

在這種方法中，我們實現一個簡單的線段樹，沒有任何最佳化技術，例如延遲傳播。

示例 1

下面的程式演示瞭如何使用 C++ 中的簡單線段樹查詢最長遞增子序列 (LIS) 的長度。構建、查詢和更新函式分別用於構建線段樹、檢索以特定元素結尾的 LIS 的最大長度以及使用新的 LIS 長度更新線段樹。lengthOfLIS 函式迭代輸入序列中的每個元素，並使用線段樹計算 LIS 長度。

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

輸出

Length of Longest Increasing Subsequence: 3

方法 2：使用帶有延遲傳播的線段樹

在這種方法中，我們實現一個帶有延遲傳播的線段樹，以進一步最佳化演算法的時間複雜度。

示例 2

下面的程式碼演示瞭如何使用帶有延遲傳播的線段樹查詢最長遞增子序列 (LIS) 的長度。這段程式碼與方法 1 的程式碼類似，因為兩種方法之間主要的區別在於線段樹的內部實現。延遲傳播技術沒有在這個程式碼中明確顯示，因為它優化了在 LIS 問題中不存在的特定用例的更新函式。但是，程式碼的基本結構保持不變，構建、查詢和更新函式以與方法 1 中類似的方式用於處理線段樹。

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

輸出

Length of Longest Increasing Subsequence: 3

結論

在這篇文章中，我們用 C++ 演示了使用線段樹確定最長遞增子序列 (LIS) 長度的方法。我們闡述了兩種方法：一種是簡單的線段樹實現，另一種是使用延遲傳播的改進方法。這兩種技術都能有效地解決 LIS 問題，其中最佳化的延遲傳播方法進一步降低了時間複雜度。