Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:如果用k表示n这个数用二进制下末尾0的个数,那么n&(-n)=2^k;In Reply To:如果用k表示n这个数用二进制下末尾0的个数,那么n&(-n)=2^k; Posted by:0810311106 at 2010-08-04 20:49:18 > 在树状数组里,这2的k次方指的是c[n]它所在子树的叶子结点的个数, > 你看图中12这个结点,12&(-12)=4,而且刚好12这个子树的叶子结点数为4,那么如果把 > 12-4+1的话,刚好就是9,12+4-1的话,就是15.那么对于任意一个数n有如下规律: > min=n-n&(-n)+1 > max=n+n&(-n)-1 > 如果想彻底弄明白这个的话,建议去详细了解一下树状数组,它有时候用处很大的,特别是求数列前n项和(多维的也行)。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator