Segment Tree Course : CodeNCode Youtube (30 July 2020 : Merge Sort Tree practice problem added)

tutorial
, ,
46 
#(Number of odd, Number of even)

def build(a, v, sl, sr):
	if sl == sr: 
		if a[sl] % 2 == 1: 
			st[v] = [1, 0]
		else: 
			st[v] = [0, 1]

		return 
	else: 
		m = (sl+sr) // 2
		build(a, 2*v, sl, m)
		build(a, 2*v + 1, m+1, sr)

		st[v][0] = st[v*2][0] + st[v*2 + 1][0]
		st[v][1] = st[v*2][1] + st[v*2 + 1][1]

def update(a, v, sl, sr, qi, nval):
	if sl == sr:
		a[sl] = nval
		if a[sl] % 2 == 1:
			st[v] = [1, 0]
		else: 
			st[v] = [0, 1]

		#a[sl] = nval
		return 

	m = (sl+sr) // 2
	if qi <= m: 
		update(a, v*2, sl, m, qi, nval)
	else: 
		update(a, v*2+1, m+1, sr, qi, nval)

	st[v][0] = st[v*2][0] + st[v*2 + 1][0]
	st[v][1] = st[v*2][1] + st[v*2 + 1][1]

def getodd(v, sl, sr, l, r):
	if sl > r or sr < l: return 0
	if sl >= l and sr <= r: return st[v][0]

	m = (sl + sr) // 2
	return getodd(2*v, sl, m, l, r) + getodd(2*v+1, m+1, sr, l, r)

def geteven(v, sl, sr, l, r):


if sl > r or sr < l: return 0
	if sl >= l and sr <= r: return st[v][1]

	m = (sl + sr) // 2
	return geteven(2*v, sl, m, l, r) + geteven(2*v+1, m+1, sr, l, r)

a = [1, 2, 3, 4, 5, 6]
st = [[None, None]]*len(a)*4
build(a, 0, 0, len(a)-1)

Here is my python code for finding number of even and odd numbers within a range. Everything is working find except the update function. It is returning wrong results. Could anyone please help me with that?

47

This is Solution of Problem Help Ashu Hackerearth

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1000000000
pair<ll,ll> seg[400004];
ll a[100001];
void build(ll s, ll e , ll tidx)
{
if(s==e)
{
if(a[s]%2==0)
{
seg[tidx].first=1;
seg[tidx].second=0;
}
else
{
seg[tidx].first=0;
seg[tidx].second=1;
}
return;
}
ll mid = (s+e)/2;
build(s,mid,2tidx);
build(mid+1,e,2tidx +1);
seg[tidx].first = seg[2tidx].first+seg[2tidx + 1].first;
seg[tidx].second = seg[2tidx].second+seg[2tidx + 1].second;
}
void update(ll s, ll e , ll tidx , ll id ,ll val)
{
if(s==e)
{
a[s]=val;
if(a[s]%2==0)
{
seg[tidx].first=1;
seg[tidx].second=0;
}
else
{
seg[tidx].first=0;
seg[tidx].second=1;
}
return;
}
ll mid=(s+e)/2;
if(mid>id)
{
update(mid+1,e,2tidx+1,id,val);
}
else
{
update(s,mid,2tidx,id,val);
}
seg[tidx].first = seg[2tidx].first+seg[2tidx + 1].first;
seg[tidx].second = seg[2tidx].second+seg[2tidx + 1].second;
}
ll queryeven(ll s, ll e , ll tidx , ll left ,ll right)
{
if(s>right||e<left)
{
return 0;
}
if(s>=left&&e<=right)
{
return seg[tidx].first;
}
ll mid=(s+e)/2;
ll a1=queryeven(s,mid,2tidx,left,right);
ll a2=queryeven(mid+1,e,2tidx +1,left,right);
return a1+a2;
}
ll queryodd(ll s, ll e , ll tidx , ll left ,ll right)
{
if(s>right||e<left)
{
return 0;
}
if(s>=left&&e<=right)
{
return seg[tidx].second;
}
ll mid=(s+e)/2;
ll a1=queryodd(s,mid,2tidx,left,right);
ll a2=queryodd(mid+1,e,2tidx +1,left,right);
return a1+a2;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
ll q;
cin>>q;
while(q–)
{
ll l,r,type;
cin>>type>>l>>r;
if(type==0)
{
if((a[l] % 2) == (r % 2)) continue;
update(1,n,1,l,r);
}
if(type==1)
{
cout<<queryeven(1,n,1,l,r)<<endl;
}
if(type==2)
{
cout<<queryodd(1,n,1,l,r)<<endl;
}
}
}
Please tell why I am getting wrong answer

48

Why it is giving WA?
NOTE- I used 0- based indexing and counted the query for even nos.

#include<bits/stdc++.h>
using namespace std;
int arr[100005];
vector<int>st;

void build(int si ,int ss,int se){
    if(ss=se){
        st[si]=(arr[ss]%2)^1;
        return;
    }
    int mid=(ss+se)/2;
    build(2*si +1,ss,mid);
    build(2*si +2,mid+1,se);
    st[si]=st[2*si +1]+st[2*si +2];
}
void update(int si ,int ss,int se,int ind,int val){
    if(ss==se){
        arr[ss]=val;
        st[si]=((val%2)^1);
        return;
    }
    int mid=(ss+se)/2;
    if(ind<=mid)update(2*si +1,ss,mid,ind,val);
    else update(2*si +2,mid+1,se,ind,val);
    st[si]=st[2*si +1]+st[2*si +2];
}
int count(int si ,int ss,int se,int qs,int qe){
    if(ss>qe || qs>se)return 0;
    if(ss>=qs && se<=qe)return st[si];
    int mid=(ss+se)/2;
    int l=count(2*si +1,ss,mid,qs,qe);
    int r=count(2*si +2,mid+1,se,qs,qe);
    return l+r;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>arr[i];
    st.resize(4*n);
    build(0,0,n-1);
    int q;cin>>q;
    while(q--){
        int a,x,y;
        cin>>a;
        if(a==0){
            // update
            cin>>x>>y;
            x--;
            update(0,0,n-1,x,y);
        }
        else if(a==1){
            // # even nos.
            cin>>x>>y;
            x--;y--;
            cout<<count(0,0,n-1,x,y)<<"\n";
        }
        else{
            // # odd nos.
            cin>>x>>y;
            x--;y--;  
            int ans=y-x+1-count(0,0,n-1,x,y);
            cout<<ans<<"\n";
        }
    }
    return 0;
}