1082 线段树练习 3

时间限制: 3 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

给你N个数，有两种操作：

1：给区间[a,b]的所有数增加X

2：询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数，

再接下来一个正整数Q，每行表示操作的个数，

如果第一个数是1，后接3个正整数，

表示在区间[a,b]内每个数增加X,如果是2，

表示操作2询问区间[a,b]的和是多少。

pascal选手请不要使用readln读入

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

1 2 3 2

2 2 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

数据范围

1<=n<=200000

1<=q<=200000

线段树：区间增减和区间查询。

 1 #include<cstdio>
 2 #define lson l,m,rt << 1 
 3 #define rson m+1,r,rt<<1|1 
 4 #define ll long long 
 5 
 6 const int N = 200010;
 7 
 8 ll sum[N<<2];
 9 ll add[N<<2];
10 int n,q;
11 
12 void pushup(int rt)
13 {
14     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
15 }
16 void pushdown(int rt,int m)  //m长度，rt线段 
17 {
18     if(add[rt])
19     {
20         add[rt<<1] += add[rt] ;
21         add[rt<<1|1] += add[rt];
22         sum[rt<<1] += add[rt] * (m - (m>>1));
23         sum[rt<<1|1] += add[rt] * (m>>1);
24         add[rt] = 0;
25     }
26 }
27 void build(int l,int r,int rt)
28 {
29     add[rt] = 0;
30     if(l==r)
31     {
32         scanf("%d",&sum[rt]);
33         return ;
34     }
35     int m = (l+r)>>1;
36     build(lson);
37     build(rson);
38     pushup(rt);    
39 }
40 void update(int L,int R,int c,int l,int r,int rt)
41 {
42     if(L<=l && r<=R)
43     {
44         add[rt] += c;
45         sum[rt] += (ll)c * (r-l+1);
46         return ;
47     }
48     pushdown(rt,r-l+1);
49     int m = (l+r)>>1;
50     if(L<=m) update(L,R,c,lson);
51     if(m<R) update(L,R,c,rson);
52     pushup(rt);
53 }
54 ll query(int L,int R,int l,int r,int rt)
55 {
56     if(L<=l && r<=R)
57     {
58         return sum[rt];
59     }
60     pushdown(rt,r-l+1);
61     ll ret=0;
62     int m = (l+r)>>1;
63     if(L<=m) ret += query(L,R,lson);
64     if(m<R) ret += query(L,R,rson);
65     return ret;
66 }
67 int main()
68 {
69     scanf("%d",&n);
70     build(1,n,1);
71     scanf("%d",&q);
72     while(q--)
73     {
74         int a,b,c,x;
75         scanf("%d",&x);
76         if(x==1)
77         {
78             scanf("%d%d%d",&a,&b,&c);
79             update(a,b,c,1,n,1);
80         }
81         else
82         {
83             scanf("%d%d",&a,&b);
84             printf("%lld
",query(a,b,1,n,1));
85         }
86     }
87     return 0;
88 }

2018-07-08

涨姿势，树状数组区间求和，区间修改。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 
 5 inline int read() {
 6     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
 7     for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
 8 }
 9 
10 const int N = 200010;
11 int a[N],b[N];
12 
13 struct BIT{
14     int n;LL c1[N],c2[N];
15     void update(int p,int v) {
16         for (int i=p; i<=n; i+=(i&(-i))) c1[i] += v,c2[i] += p*v;
17     }
18     LL query(int p) {
19         LL ans = 0;
20         for (int i=p; i; i-=(i&(-i))) ans += (p+1)*c1[i]-c2[i];
21         return ans;
22     }
23 }bit;
24 
25 int main() {
26     int n = read(),last = 0;
27     bit.n = n;
28     for (int i=1; i<=n; ++i) {
29         int tmp = read();
30         a[i] = tmp - last;
31         last = tmp;
32     }
33     for (int i=1; i<=n; ++i) 
34         bit.update(i,a[i]);
35         
36     int m = read();
37     while (m--) {
38         int opt = read();
39         if (opt == 1) {
40             int l = read(),r = read(),v = read();
41             bit.update(l,v);
42             if (r < n) bit.update(r+1,-v);
43         }
44         else {
45             int l = read(),r = read();
46             printf("%lld
",bit.query(r)-bit.query(l-1));
47         }
48     }
49     return 0;
50 }