线段树引例

题目:序列为n,将第i个数加或减x,求l到r的和
样例: 7
1 4 5 6 3 2 7
输出:5
2

#include<bits/stdc++.h>
using namespace std;
int const N=1e3+7;
int n;
int a[N];
int tree[N<<2];  //(N<<1)<<1 //N表示叶子节点的个数,
//第一次 <<1 表示要给除叶子以外的其他节点开空间;第二次是给最后一层的下一层开空间,用来判断叶子是否是真的叶子(即判断叶子是否有儿子) 
void bulid(int p,int l,int r){  //p表示tree的下标  //l,r分别表示a数组中的区间左右边界 
    if(l==r) { tree[p]=a[l]; return ; }
    int mid=(l+r) >> 1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    tree[p]=tree[p*2]+tree[p*2+1];
}
void add(int p,int l,int r,int p_a,int num){ //p_a表示a数组第p个元素 //p_a,num 表示把第p_a个数加上num 
    if(l==r) { tree[p]+=num;return ; }
    int mid=(l+r) >> 1;
    if(p_a<=mid) add(p*2,l,mid,p_a,num);
    else add(p*2+1,mid+1,r,p_a,num);
    tree[p]=tree[p*2]+tree[p*2+1];
}
int ask(int p,int l,int r,int x,int y){ //(l,r)表示当前区间,(x,y)表示目标区间 
    if(x<=l&&r<=y) return tree[p];
    int mid=(l+r)>>1;
    //第一种搜索方法 
    int res=0;
    if(x<=mid) res+=ask(p*2,l,mid,x,y);
    if(y>=mid+1) res+=ask(p*2+1,mid+1,r,x,y); 
    return res;
    //第二种搜索方法  
    //if(y<=mid) return ask(p*2,l,mid,x,y); 
    //if(x>=mid+1) return ask(p*2+1,mid+1,r,x,y);
    //return ask(p*2,l,mid,x,mid)+ask(p*2+1,mid+1,r,mid+1,y);
}
int main(){
    cin >> n;
    for(int i=1;i<=n;++i) cin >> a[i];
    bulid(1,1,n);
    cout << ask(1,1,n,1,2) << endl;
    add(1,1,n,2,-3);
    cout << ask(1,1,n,1,2) << endl;
    return 0; 
}
全部评论

相关推荐

小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
昨天 12:04
门头沟学院 Java
现在是很缺人吗
码农索隆:缺分母,不缺分子,这样好作为炫耀的资本
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务