Created
September 26, 2015 03:49
-
-
Save mangalvikas/a9d9f9e3cf4c72ce2ff2 to your computer and use it in GitHub Desktop.
Help Ashu | Simple Segment tree
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| int tree[2*100000+4]={0}; | |
| long long int a[100000+4]; | |
| void build(int node,int start,int end) | |
| { | |
| if(start==end) | |
| { | |
| if(a[start]%2==0) | |
| tree[node]=1; | |
| else | |
| tree[node]=0; | |
| } | |
| else | |
| { | |
| int mid=(start+end)/2; | |
| build(2*node,start,mid); | |
| build(2*node+1,mid+1,end); | |
| tree[node]=tree[node*2]+tree[2*node+1]; | |
| } | |
| } | |
| int queri(int node,int start,int end,int l,int r) | |
| { | |
| if(r<start || l>end) | |
| { | |
| return 0; | |
| } | |
| else | |
| { | |
| if(l<=start && end<=r) | |
| return tree[node]; | |
| else{ | |
| int mid = (start+end)/2; | |
| int p1 = queri(2*node,start,mid,l,r); | |
| int p2 = queri(2*node+1,mid+1,end,l,r); | |
| return p1+p2;} | |
| } | |
| } | |
| void update(int node,int start,int end,int ind,long long int val) | |
| { | |
| if(start==end) | |
| { | |
| a[ind]==val; | |
| if(val%2==0) | |
| tree[node]=1; | |
| else | |
| tree[node]=0; | |
| } | |
| else | |
| { | |
| int mid = (start+end)/2; | |
| if(mid<ind && ind<=end) | |
| update(2*node+1,mid+1,end,ind,val); | |
| else | |
| update(2*node,start,mid,ind,val); | |
| tree[node]=tree[2*node]+tree[2*node+1]; | |
| } | |
| } | |
| int main() { | |
| // your code goes here | |
| int n,i,q,x,y; | |
| long long int z; | |
| scanf("%d",&n); | |
| for(i=1;i<=n;i++) | |
| { | |
| scanf("%lld",&a[i]); | |
| } | |
| build(1,1,n); | |
| scanf("%d",&q); | |
| for(i=0;i<q;i++) | |
| { | |
| scanf("%d%d%lld",&x,&y,&z); | |
| if(x==1) | |
| printf("%d\n",queri(1,1,n,y,z)); | |
| if(x==2) | |
| printf("%d\n",z-y+1-queri(1,1,n,y,z)); | |
| if(x==0) | |
| update(1,1,n,y,z); | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment