JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
segment tree(how to optimise) | Reply
There are N coins kept on the table, numbered from 1 to N.
Initially, each coin is kept tails up. You have to perform two types of operations :

1) Flip all coins numbered between A and B. This is represented by the command "0 A B"

2) Answer how many coins numbered between A and B are heads up. This is represented by the command "1 A B".

my update on count functions are

l=1,h=N;
[s,e] is query interval.

void update(int node, int c[], int l, int h, int s, int e){
if(l==h&&((s<=l&&l<=e))){
c[node]=!c[node];
}
if(l<h){
update(node><<1, c, l, (l+h)>>1, s, e);
update((node<<1)+1, c, ((l+h)>>1)+1, h, s, e);
c[node]=c[(node<<1)]+c[(node<<1)+1];
}
}

int count(int node, int c[], int l, int h, int s, int e){
if(s>h||e<l){
return 0;
}
if(s><=l&&e>=h){
return c[node];
}

int n1=count(node<<1, c, l,(l+h)>>1, s, e);
int n2=count((node<<1)+1, c, ((l+h)>>1)+1, h, s, e);
return n1+n2;
}
anyone please tell me how can i further optimize it?

thank you.
RSS