首页 > 代码库 > JL一定不会的——重口味线段树

JL一定不会的——重口味线段树

 注意求M的地方:for(M=1;M<=n+1;M*=2);

和老言争论了半天的n后面是否+1(是否进行越界处理),后来得出的结论是:

+1,浪费空间;

不加,遇到特殊情况有安全隐患,但证明,对于t,如果为偶数,则不进行处理,所以,可以不加.

技术分享
 1 int Query(int s,int t){ 2     int ans=0; 3     for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){ 4         if(~s&1) ans+=T[s^1];//如果是左子树的左孩子,则处理左子树右孩子 5         if( t&1) ans+=T[t^1];//如果是右子树的左孩子,则处理右子树左孩子 6     } 7     return ans; 8 } 9 void Add(int n,int V){10     for(T[n+=M]+=V,n>>=1;n;n>>=1){11         T[n]=T[n+n]+T[n+n+1];12     }13 }14 void Sub(int n,int V){15     for(T[n+=M]-=V,n/=2;n;n/=2){16         T[n]=T[n*2]+T[n*2+1];17     }18 }19 void build_tree(int n){20     int i;21     for(M=1;M<=n+1;M*=2)//计算M22     for(i=M+1;i<=M+n;i++){23         scanf("%d",&T[i]);24     }25     for(i=M-1;i>0;i--) T[i]=T[i*2]+T[i*2+1];26 }
核心代码

这个东西,估计某人一定不会。

至于JL是谁,详见博客——翻译

JL一定不会的——重口味线段树