首页 > 代码库 > 【线段树】线段树系列 0.1单点修改单点求和线段树

【线段树】线段树系列 0.1单点修改单点求和线段树

终于搞定了单点修改线段树。。。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;    }}

 

【线段树】线段树系列 0.1单点修改单点求和线段树