查詢字串中某個範圍內第K個最大的字符，帶有更新操作

芬威克樹是一種資料結構，它能夠以O(log n) 時間複雜度進行範圍更新和範圍搜索，也稱為二元索引樹(BIT)

基本概念是為字串中的每個字母保留頻率數組，第 i 個字元的頻率記錄在頻率數組中的索引 i 處。然後，頻率數組可以允許使用 Fenwick Tree 進行範圍更新和範圍查詢。

問題處理

您可以使用以下查詢從字串中提取第 K 個最大字符，更新範圍為 [L, R] -

• 建構線段樹 - 首先建立線段樹，其中儲存字串中每個字元的頻率。線段樹的每個節點中儲存有一個包含該範圍內每個字母的頻率的頻率數組，它代表字串中索引的範圍。

• 更新 - 透過降低某些先前字元的頻率並增加新字元的頻率，您可以透過更新線段樹中的匹配葉節點來更新字串中的字元。

  李>

• 第K 個最大字元搜尋 - 從線段樹的根開始，遞歸地轉到索引的相關範圍[L, R] 以找到該範圍內的第K 個最大字符。使用修改後的二分搜尋可以在每個節點找到該範圍內的第 K 個最大字元。

• 時間複雜度 - 為 O (log n)，這裡 n 是字串的長度。線段樹的空間複雜度為 O(n)。

文法

假設字串最初給定並且可以更新，查詢是在字串的區間[L, R]中查找第k個最大的字符，可以使用以下語法 -

1.初始化字串 -

string str = "initial_string";

2.更新索引處的字串 -

str[index] = new_character;

3.找出區間 [P, T] 中第 k 個最大的字元 -

// initialize frequency array of size 26 
int freq[26] = {0};

// count the frequency of each character in the range
for (int i = P; i <= T; i++) {
   freq[str[i] - 'a']++;
}

// find k th greatest character
int cont = 0;
for (int i = 25; i >= 0; i--) {
   cont += freq[i];
   if (cont >= k) {
      return (char) (i + 'a');
   }
}

// if k th is larger than total no. of different characters in interval,

// give special character or throw exception

演算法

從給定的區間 [L, R] 中找出第 K 個最大字元並進行一些更新的演算法 -

• 步驟 1 - 初始化大小為 26 的陣列 A，其中每個元素 A[i] 表示字串中第 i 個字元（從 0 開始索引）的計數。

• 步驟 2 - 從左到右遍歷字串 S 並更新陣列 A 中每個字元的計數。

• 第 3 步 - 若要處理更新，請維護與 A 大小相同的單獨陣列 B，並初始化為零。

• 步驟 4 - 每當執行更新操作時，將新舊字元計數之間的差異新增至 B 中的對應元素。

• 步驟5 - 要找到區間[L, R] 中第K 個最大的字符，計算A 和B 到索引R 的累積和，並減去A 和B 的累積和直至索引L-1。這給出了應用更新後範圍 [L, R] 中每個字元的計數。

• 第 6 步 - 依計數降序對 [L, R] 範圍內的字元進行排序。

• 第 7 步 - 依排序順序傳回第 K 個字元。

遵循的方法

方法1

在此範例中，字串「abacaba」用作初始字串。建構函數透過計算字串中每個字元的出現次數來初始化線段樹。更新函數透過先遞減舊字元的計數然後遞增新字元的計數來更新字串和線段樹。查詢函數使用二分查找傳回 [L,R] 中第 k 個最大的字元。

範例 1

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+5;

struct NODE {
   int E, F, cnt[26];
} tree[4*N];

string W;

void build(int X, int E, int F) {
   tree[X].E = E, tree[X].F = F;
   if(E == F) {
      tree[X].cnt[W[E]-'a']++;
      return;
   }
   int mid = (E+F)/2;
   build(2*X, E, mid);
   build(2*X+1, mid+1, F);
   for(int i=0; i<26; i++) {
      tree[X].cnt[i] = tree[2*X].cnt[i] + tree[2*X+1].cnt[i];
   }
}

void update(int X, int E, int F, int idx, char ch) {
   if(E == F) {
      tree[X].cnt[W[E]-'a']--;
      W[E] = ch;
      tree[X].cnt[W[E]-'a']++;
      return;
   }
   int mid = (E+F)/2;
   if(idx <= mid) {
      update(2*X, E, mid, idx, ch);
   } else {
      update(2*X+1, mid+1, F, idx, ch);
   }
   for(int i=0; i<26; i++) {
      tree[X].cnt[i] = tree[2*X].cnt[i] + tree[2*X+1].cnt[i];
   }
}

int QUERY(int X, int E, int F, int k) {
   if(E == F) {
      return E;
   }
   int mid = (E+F)/2;
   int cnt = 0;
   for(int i=0; i<26; i++) {
      cnt += tree[2*X].cnt[i];
   }
   if(k <= cnt) {
      return QUERY(2*X, E, mid, k);
   } else {
      return QUERY(2*X+1, mid+1, F, k-cnt);
   }
}

int main() {
   W = "abacaba";
   int n = W.length();
   build(1, 0, n-1);

   cout << W << endl;

   update(1, 0, n-1, 4, 'd');

   cout << W << endl;

   int P = 5;
   int Q = 2;
   int R = 6;
   cout << QUERY(1, 0, n-1, R) << endl;
   cout << QUERY(1, 0, n-1, Q+P-1) << endl;
   return 0;
}

輸出

abacaba
abacdba
5
5

方法2

程式首先初始化一個大小為 N x 26 的二維陣列 freq，其中 freq[i][j] 表示字串 s 的前綴中第 j 個字元直到第 i 個索引的頻率。然後，對於每個索引 i，我們透過增加第 i 個索引處的字元計數並新增所有先前字元的計數來更新 freq 陣列。

初始化 freq 陣列後，我們執行兩個查詢。在每個查詢中，我們透過從索引 R 的計數中減去索引 L-1 之前的字元計數來計算 [L, R] 範圍內的字元計數。然後，我們從 0 到 25 迭代字元頻率，追蹤到目前為止看到的字元數。當我們到達第 K 個最大的字元時，我們儲存它的索引並跳出循環。最後，我們列印與儲存的索引對應的字元。

在兩次查詢之間，我們透過將索引 4 處的字元變更為「a」來更新字串。為了有效地更新 freq 數組，我們更新相應索引處新舊字元的計數，然後使用更新後的前綴和重新計算所有後續字元的計數。

範例 1

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
int Freq[N][26];

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);

   string Y = "programming code";
   int U = Y.size();

   for (int i = 0; i < U; i++) {
      Freq[i+1][Y[i]-'a']++;
      for (int j = 0; j < 26; j++) {
         Freq[i+1][j] += Freq[i][j];
      }
   }

   int Q = 2;
   while (Q--) {
      int l = 2, r = 9, k = 3;
      int cont = 0, ans;
      for (int i = 0; i < 26; i++) {
         cont += Freq[r][i] - Freq[l-1][i];
         if (cont >= k) {
            ans = i;
            break;
         }
      }
      cout << "The " << k << "rd greatest character in range [" << l << "," << r << "] is " << char(ans+'a') << "\n";

      Y[4] = 'a'; // update
      for (int i = 4; i < U; i++) {
         Freq[i+1][Y[i]-'a']++;
         Freq[i+1][Y[i-4]-'a']--;
         for (int j = 0; j < 26; j++) {
            Freq[i+1][j] += Freq[i][j];
         }
      }
   }

   return 0;
}

輸出

The 3rd greatest character in range [2,9] is i
The 3rd greatest character in range [2,9] is a

結論

最後，利用線段樹和二分搜尋方法的組合可以有效地解決識別具有更新的區間[L，R]中第K個最大字元的請求。二分查找技術用於定位該範圍內的第 K 個最大字符，線段樹用於追蹤某個範圍內字符的出現頻率。

以上是查詢字串中某個範圍內第K個最大的字符，帶有更新操作的詳細內容。更多資訊請關注PHP中文網其他相關文章！