codevs 1081 线段树练习 2 线段树-白红宇

codevs 1081 线段树练习 2 线段树

阅读量：4951 次

发布时间：2019-06-11

本文共 2115 字，大约阅读时间需要 7 分钟。

题目描述

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

1 2 3 2

2 3

样例输出

Sample Output

数据范围及提示

Data Size & Hint

数据范围

1<=n<=100000

1<=q<=100000

思路：线段树裸题（延迟标记都不用，数据好水）；

线段树：

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  #define true ture#define false flaseusing namespace std;#define ll long longint scan(){ int res = 0 , ch ; while( !( ( ch = getchar() ) >= '0' && ch <= '9' ) ) { if( ch == EOF ) return 1 << 30 ; } res = ch - '0' ; while( ( ch = getchar() ) >= '0' && ch <= '9' ) res = res * 10 + ( ch - '0' ) ; return res ;}struct is{ int l,r; int num;}tree[200010*3];void build_tree(int l,int r,int pos){ tree[pos].l=l; tree[pos].r=r; if(l==r) { //tree[pos].num=1; scanf("%d",&tree[pos].num); return; } int mid=(l+r)/2; build_tree(l,mid,pos*2); build_tree(mid+1,r,pos*2+1); tree[pos].num=tree[pos*2].num+tree[pos*2+1].num;}void update(int l,int r,int change,int pos){ if(tree[pos].l==l&&tree[pos].r==r&&l==r) { tree[pos].num+=change; return; } int mid=(tree[pos].l+tree[pos].r)/2; if(r<=mid) update(l,r,change,pos*2); else if(l>mid) update(l,r,change,pos*2+1); else { update(l,mid,change,pos*2); update(mid+1,r,change,pos*2+1); } tree[pos].num=tree[pos*2].num+tree[pos*2+1].num;}int query(int l,int r,int pos){ //cout<
                   
                    <<" "<
                    
                     <<" "<
                     
                      <
                      
                       mid) return query(l,r,pos*2+1); else if(r<=mid) return query(l,r,pos*2); else return query(l,mid,pos*2)+query(mid+1,r,pos*2+1);}int main(){ int x,q,i,t; while(~scanf("%d",&x)) { build_tree(1,x,1); scanf("%d",&q); while(q--) { int flag,change,l,r; scanf("%d%d",&flag,&l); if(flag==1) { scanf("%d%d",&r,&change); update(l,r,change,1); } else printf("%d\n",query(l,l,1)); } } return 0;}

View Code

转载于:https://www.cnblogs.com/jhz033/p/5397788.html

你可能感兴趣的文章