Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:如果用k表示n这个数用二进制下末尾0的个数,那么n&(-n)=2^k;

Posted by maxh123ok1 at 2011-07-22 09:51:40 on Problem 2309
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator