终于搞定了单点修改线段树。。。3个月。。操蛋。。根本没有模板题。。觉得太弱了。。。艹蛋。。。必须进一步更新我的版本啊
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; struct node { int left,right,value; }; node point[100]; int father[100]; int g; void buildtree(int i,int left,int right) { father[i]=(int)floor(i)/2.0; point[i].left=left; point[i].right=right; point[i].value=0; if (left==right) {father[i]=i;} else { buildtree(i<<1, left, (int)floor( (right+left) / 2.0)); buildtree((i<<1) + 1, (int)floor( (right+left) / 2.0) + 1, right); } } //---------------------------------------------------------------------------- void update(int x,int add,int left,int right,int now) //left，right是范围，add是加上的值，now是当前节点的标号，x是目标节点 { int mid=(left+right)>>1; point[now].value+=add; if ( (right-left)<1 ) {g=left; return;} if ( (left<=x) && (x<=mid) ) { update(x,add,left,mid,2*now); } if ( ((mid+1)<=x) && (x<=right) ) { update(x,add,mid+1,right,2*now+1); } } //---------------------------------------------------------------------------- int search(int x,int now) { if (point[now].left==point[now].right) {return (point[now].value);} int mid=(point[now].left+point[now].right)>>1; if ( (point[now].left<=x) && (x<=mid) ) { return (search(x,2*now)); } if ( ((mid+1)<=x) && (x<=point[now].right) ) { return (search(x,2*now+1)); } return 598460606; } //---------------------------------------------------------------------------- int main() { int n,m,k; cin>>n; buildtree(1,1,n); for (int i=1;i<=n;i++) { int x,ad; cin>>x>>ad; update(x,ad,1,n,1); } cin>>m; for (int i=1;i<=m;i++) { int x,ad; cin>>x>>ad; update(x,ad,1,n,1); } cin>>k; for (int i=1;i<=k;i++) { int s; cin>>s; cout<<search(s,1)<<endl; } }