芬威克树是一种数据结构，它能够以 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 个最大字符，线段树用于跟踪某个范围内字符的出现频率。
