1081 线段树练习 2
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
给你N个数，有两种操作
1：给区间[a,b]的所有数都增加X
2：询问第i个数是什么？
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是2，后面跟1个整数i, 表示询问第i个位置的数是多少。
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 3
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
数据范围
1<=n<=100000
1<=q<=100000
代码一：
codevs 1081 #include<cstdio> #include<iostream> using namespace std; int n,m; int sz[100010]; struct node { int val,delta,l,r; node * cl,*cr; }* root=NULL; int sv(node * cur) { return cur?cur->val:0; } void down(node * cur) { if(cur->cl) { cur->cl->delta+=cur->delta; cur->cl->val+=cur->delta*(cur->cl->r-cur->cl->l+1);//叶节点是有用的，其余的区间是没用的 } if(cur->cr) { cur->cr->delta+=cur->delta; cur->cr->val+=cur->delta*(cur->cr->r-cur->cr->l+1); } cur->delta=0; } void build(node * &cur,int l,int r) { if(r<l)return; cur=new node; cur->l=l;cur->r=r;cur->delta=0; if(l==r) { cur->val=sz[l]; cur->cl=cur->cr=NULL; } else { int mid=(l+r)/2; build(cur->cl,l,mid); build(cur->cr,mid+1,r); //不用更新当前的val，因为题目中没说要求区间的值 } } int query(node * cur,int pos) { if(cur->l==cur->r)return cur->val; if(cur->delta)down(cur);/**/ int mid=(cur->l+cur->r)/2; if(pos<=mid)return query(cur->cl,pos);/*一定是return，，否则就从最里面返回一个数，不会返回到主函数*/ else return query(cur->cr,pos); } void add(node * cur,int l,int r,int delta) { if(l<=cur->l&&cur->r<=r) { cur->delta+=delta;/*记录当前区间欠这个区间内的每个数多少*/ cur->val+=delta;//当cur是叶节点时，有用 return; } int mid=(cur->l+cur->r)/2; if(cur->delta)down(cur);/*如果要取这个区间的一部分加上delta的话，先把这个区间欠下面的数传下去，而不是先加上delta，因为这样直接加会把区间的其他部分多加了delta*/ if(l<=mid)add(cur->cl,l,r,delta); if(mid<r)add(cur->cr,l,r,delta); } int main() { cin>>n; for(int j=1;j<=n;j++)scanf("%d",&sz[j]); build(root,1,n); cin>>m; for(int i=0;i<m;i++) { int a,b,c,d; scanf("%d",&a); if(a==1) { scanf("%d%d%d",&b,&c,&d); add(root,b,c,d); } else if(a==2) { scanf("%d",&b); printf("%d ",query(root,b)); } } return 0; }
代码二：
#include<cstdio> #include<iostream> using namespace std; #define INF 100001 int sz[INF]; struct node { int l,r,delta; node *child[2]; int val; }*root=NULL; int n,q,a,b,c,x; void input() { scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&sz[i]); } void update(node *cur) { cur->val=cur->child[0]->val+cur->child[1]->val; } void bulid(node *&cur,int l,int r) { if(l>r) return ; cur=new node; cur->l=l;cur->r=r; cur->delta=0; if(l==r) { cur->child[0]=cur->child[1]=NULL; cur->val=sz[l]; } else { int mid=(l+r)/2; bulid(cur->child[0],l,mid); bulid(cur->child[1],mid+1,r); // update(cur); } } void down(node * cur) { if(cur->child[0]) { cur->child[0]->delta+=cur->delta; cur->child[0]->val+=cur->delta*(cur->child[0]->r-cur->child[0]->l+1); } if(cur->child[1]) { cur->child[1]->delta+=cur->delta; cur->child[1]->val+=cur->delta*(cur->child[1]->r-cur->child[1]->l+1); } cur->delta=0; } void add(node* cur,int l,int r,int delta) { if(cur->l>=l&&cur->r<=r) { cur->delta+=delta; cur->val+=delta*(cur->l-cur->r+1); return ; } int mid=(cur->l+cur->r)/2; if(cur->delta) down(cur); if(l<=mid) add(cur->child[0],l,r,delta); if(r>mid) add(cur->child[1],l,r,delta); } int query(node* cur,int x) { if(cur->l==cur->r) { return cur->val; } if(cur->delta) down(cur); int mid=(cur->l+cur->r)/2; if(x<=mid) return query(cur->child[0],x); else return query(cur->child[1],x); } int main() { input(); bulid(root,1,n); scanf("%d",&q); while(q--) { scanf("%d",&x); if(x==1){ scanf("%d%d%d",&a,&b,&c); add(root,a,b,c); } else { scanf("%d",&a); printf("%d ",query(root,a)); } } return 0; }