本页链接均可单机跳转，网址过长的只给出超链接
背包九讲 pdfhttps://github.com/tianyicui/pack/blob/master/V2.pdf
wzk线段树笔记http://wyfcyx.logdown.com/posts/201802-summary-data-structures-zkw-segment-tree-details
1 #include<cstdio> 2 #include<iostream> 3 #define M 261244 4 using namespace std; 5 int tr[524289]; 6 void query(int s,int t)//查询[s,t]区间和 7 { 8 int ans=0; 9 //s=s+M-1,t=t+M+1 先将s,t扩展为开区间再 +M找叶子 10 for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1)//s^t^1当s，t为左右兄弟时结束 11 12 { 13 if(~s&1)ans+=tr[s^1];//s有右兄弟 14 if(t&1)ans+=tr[t^1];//t有左兄弟 15 } 16 printf("%d ",ans); 17 } 18 void change(int x,int y) 19 { 20 for(tr[x+=M]+=y,x>>=1;x;x>>=1) 21 tr[x]=tr[x<<1]+tr[x<<1|1]; 22 } 23 int main() 24 { 25 int n,m,f,x,y; 26 scanf("%d",&n); 27 for(int i=1;i<=n;i++){scanf("%d",&x);change(i,x);} 28 scanf("%d",&m); 29 for(int i=1;i<=m;i++) 30 { 31 scanf("%d%d%d",&f,&x,&y); 32 if(f==1)change(x,y); 33 else query(x,y); 34 } 35 return 0; 36 } 37 //http://hzwer.com/913.html
1 for(M=1;M<(n+2);M<<=1);
M值的循环分号一定要记得写，啊啊啊啊啊啊啊！！！
另外s^t^1看成t-s>1就好