首页 > 代码库 > 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一定不会的——重口味线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。