In this HackerEarth Shil and Palindrome Research problem solution Shil got interested in palindrome research. For that he needs some research data for a particular string S. To obtain this data he has some queries of following type:
1. L x - update Lth character of string to x
2. L R - find if all the character of string from index L to R can be rearranged such that they can form a palindrome. If they can print "yes", else print "no".
Since you decided to help Shil with his research, its your responsibililty to make this data available as soon as possible.

## HackerEarth Shil and Palindrome Research problem solution.

```#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define f first
#define s second
#define mod 1000000007
#define inf 1e8

#define pi pair<ll,ll>
#define pii pair<pi,ll>
#define f first
#define mp make_pair
#define pb push_back
#define s second
#define rep(i,n) for(int i=0;i<n;i++)
#define forup(i,a,b) for(int i=a;i<=b;i++)
int bt[100011][26];
int N,Q;
void update(int ind ,int val,int pos){
while(ind<=N){
bt[ind][pos]+=val;
ind+=(ind&-ind);
}
}
int query(int ind,int pos){
int ans=0;
while(ind>0){
ans+=bt[ind][pos];
ind-=(ind&-ind);
}
return ans;
}
int main(){
freopen("input-12.txt","r",stdin);
freopen("output-12.txt","w",stdout);
cin >> N >> Q;
string S;
cin >> S;
rep(i,N){
update(i+1,1,S[i]-'a');
}
int t,L,R;
char x;
while(Q--){
cin >> t;
if(t==1){
cin >> L >> x;
update(L,1,x-'a');
update(L,-1,S[L-1]-'a');
S[L-1]=x;
}
else{
cin >> L >> R;
int odd=0;
int cur;
rep(i,26){
cur=query(R,i)-query(L-1,i);
if(cur%2){
odd++;
}
}
if(odd<=1){
cout<<"yes\n";
}
else{
cout<<"no\n";
}
}
}
}```

### Second solution

```#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
#define max 100002
ll power(ll a, ll b) {
ll x = 1, y = a;
while(b > 0) {
if(b%2 == 1) {
x=(x*y);
if(x>mod) x%=mod;
}
y = (y*y);
if(y>mod) y%=mod;
b /= 2;
}
return x;
}
ll tree[max][27];

ll read(ll idx, ll i) {
ll sum = 0;
while (idx > 0) {
sum += tree[idx][i];
idx -= (idx & -idx);
}
return sum;
}
void update(ll idx ,ll val, ll i) {
while (idx <= max) {
tree[idx][i] += val;
idx += (idx & -idx);
}
}
int main()
{
int n,q,x,l,r;
cin>>n>>q;
string str;
char c;
cin>>str;
memset(tree,0,sizeof(tree));
for(int i = 0; i < n; i++) {
update(i+1,1,str[i]-97+1);
}
while(q--) {
cin>>x;
if(x == 1) {
cin>>l>>c;
update(l,-1,str[l-1]-97+1);
str[l-1] = c;
update(l,1,str[l-1]-97+1);
}
else {
cin>>l>>r;
int c = 0;
for(int i = 1; i <= 26; i++) {
if(l == 1) {
c++;
}
}
else {