#include <bits/stdc++.h>
using namespace std;
struct treeNode {
int square_sum;
};
void buildTree(string s, treeNode* tree,
int start, int end,
int treeNode)
{
if (start == end) {
tree[treeNode].square_sum
= pow(s[start] - 'a' + 1, 2);
return;
}
int mid = start + ((end - start) / 2);
buildTree(s, tree, start,
mid, 2 * treeNode);
buildTree(s, tree, mid + 1,
end, 1 + 2 * treeNode);
tree[treeNode].square_sum
= tree[(2 * treeNode)].square_sum
+ tree[(2 * treeNode) + 1].square_sum;
}
int querySquareSum(treeNode* tree, int start,
int end, int treeNode,
int l, int r)
{
if ((l > end) || (r < start)) {
return 0;
}
if ((l <= start) && (r >= end)) {
return tree[treeNode].square_sum;
}
int mid = start + ((end - start) / 2);
int X = querySquareSum(tree, start,
mid, 2 * treeNode,
l, r);
int Y = +querySquareSum(tree, mid + 1, end,
1 + 2 * treeNode, l, r);
return X + Y;
}
void updateTree(string s, treeNode* tree,
int start, int end,
int treeNode, int idx, char X)
{
if ((start == end) && (idx == start)) {
s[idx] = X;
tree[treeNode].square_sum
= pow(X - 'a' + 1, 2);
return;
}
int mid = start + ((end - start) / 2);
if (idx <= mid) {
updateTree(s, tree, start, mid,
(2 * treeNode), idx, X);
}
else {
updateTree(s, tree, mid + 1, end,
(2 * treeNode) + 1, idx, X);
}
tree[treeNode].square_sum
= tree[(2 * treeNode)].square_sum
+ tree[(2 * treeNode) + 1].square_sum;
}
void PerformQuery(string S,
vector<vector<string> > Q)
{
int n = S.size();
treeNode* tree = new treeNode[(4 * n) + 1];
for (int i = 0; i <= (4 * n); i = i + 1) {
tree[i].square_sum = 0;
}
buildTree(S, tree, 0, n - 1, 1);
for (int i = 0; i < Q.size(); i++) {
if (Q[i][0] == "S") {
int L = stoi(Q[i][1]);
int R = stoi(Q[i][2]);
cout << querySquareSum(tree, 0,
n - 1, 1, L, R)
<< endl;
}
else if (Q[i][0] == "U") {
int I = stoi(Q[i][1]);
updateTree(S, tree, 0, n - 1,
1, I, Q[i][2][0]);
}
}
}
int main()
{
string S = "geeksforgeeks";
vector<vector<string> > Q = { { "S", "0", "2" },
{ "S", "1", "2" },
{ "U", "1", "a" },
{ "S", "0", "2" },
{ "S", "4", "5" } };
PerformQuery(S, Q);
}
Original page link
Best Cool Tech Gadgets
Top favorite technology gadgets
0 comments:
Post a Comment