資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在字串範圍內查詢第 K 大字元並進行更新的查詢
Fenwick 樹是一種資料結構，它能夠以 O(log n) 的時間複雜度執行範圍更新和範圍搜尋，也稱為二進位制索引樹 (BIT)。
基本概念是為字串中的每個字母維護一個頻率陣列，其中第 i 個字元的頻率記錄在頻率陣列的索引 i 處。然後，頻率陣列可以使用 Fenwick 樹進行範圍更新和範圍查詢。
問題方法
您可以使用以下查詢從字串中提取第 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”用作初始字串。build 函式透過計算字串中每個字元的出現次數來初始化線段樹。update 函式透過首先遞減舊字元的計數，然後遞增新字元的計數來更新字串和線段樹。query 函式使用二分查詢返回 [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 陣列後，我們執行兩個查詢。在每個查詢中，我們透過從索引 L-1 處的字元計數中減去索引 R 處的字元計數來計算範圍 [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 大字元，而線段樹用於跟蹤範圍內字元的頻率。
255 次檢視
