数据结构
网络
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 次查看
