JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor segment tree(how to optimise)
 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 arel=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<<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&&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.
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor segment tree(how to optimise) Previous Thread  |  Next Thread