线段树——区间修改和求和(板子题)

一个简单的整数问题2

原题

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

  1. C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
  2. Q l r，表示询问数列中第 l∼r 个数的和。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数 N,M,。

第二行 N 个整数 A[i]。

接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

1≤N,M≤105
|d|≤10000
|A[i]|≤109

输入样例：

1
2
3
4
5
6
7
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例：

1
2
3
4
4
55
9
15

思路(百度之星之后准备开视频讲解)

​ 持续更新中……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
/**
                                                                                   .@@
                                                                                  .@@@@
                                                     :--:::::::-----==:           %%@@@%
                                             :*++*+==--========----------:-==:    @%@@@@.
                                        .:. ..-=+=+*+==---=----------------------:*@%@@@@         .:..
                                    .::::-----==+++====+***#+----=------:--------:-=%%@@@#+%@@@@@@@@@@@@@@@@@@@@@@@
                :+%@@@@@@@@@@@@@@%::::=*=+++++=++==*%*=-:=*#+##=-----------------:::-@%@@@@@@@@@@@@@@@@@@@@@@@@@@@*
             %%%%%%%%%%%%@@@@@@= .:=%@@@@@%#+=+++%@@@%+-==--++-=*=-------------:-----:*@@@@@@@@@@@@@@@@@@@@@@@@@@%
             .@%%%%%%%%%@@@@%-  .-+%@@@%@%%%####%#*#%%%%==----+=:-++-::------=----:::-:=@@@@@@@@@@@@@@@@@@@@@@@@%
               %%%%%%%%@%@@+  .::*%@@@@%#**#####******+*%+===---+=..:==---------:---::::-@@@@@@@@@@@@@@@@@@@@@@@
                %%%@%@%@@@:  .:.%%%%%#=+*+*+*#*+=+***+*#+##=--=-:-+.   ==--------::::--::-@@@@@@@@@@@@@@@@@@@@@
                .#%%%@%@%   . -@%%%*==+*++++**+++=+*++=++=+#--=----=:    +---:-::::::::--:-%@@@@@@@@@@@@@@@@@@=
                 :@%%%@=   . =%%%#---======+=========++=====*+--=-=--=.    --::::::::::::--=@@@@@@@@@@@@@@@@@@@:
                  @%@#   .  -%%*+---========-:===++======-==-==--=-----:     :-::::::::::::-=@@@@@@@@@@@@@@@@@@@=
                  @#.   .  .#*=+.-=-==-==-=-::===+=-==-=--=--==+=:------=     .-:::::::-:--:--#@@@@@@@@@@@@@@@@@@#
                 -         #+=-.:----=------.:-=-*===----==--==-+=-:::-::-:     :-::::::::::::==+@@@@@@@@@@@@@@@@@@
                     .    -==:..-=--==--:--:.-===+====----=====--=--::::::--      ::::::::::--:=%*=*@@@@@@@@@@@@@@@@.
                .+: .    .==-. :----==-::--:.---==-===---:------:----::::::-+       -:::------=--+#+#@@@@@@@@@@@@@@@@.
              .  . -    ::--. .::---:-:.-=-: :--==--==:=--:-::::::--=-:::-:::*.      :::-==-==--:--**@@@@@@@%@@@@@@@@@=
                :.:     :::.. .--:::::: --::.:-:---:--:--:::::::::--:==:::::::+.       -:-=-=------:*+@@@@@@@@+ #@@@@@@
               #-.     -::.. .=+:::::-:.--:-:.::::::::::+:::::::::::::=-:::::::=.       :=-=---------=%@@@@@@@@@  :@@@@
             =@-.     :=..   -=::::-:=.:::::-.::::::::::%.::::::::::::-=:::::::-+-        *%+=-------::%@@@@@@@@@:   :.
            #@*.      +-..  :-:::::::-..::::::.:::::::::%:-==:..::::::--+:::-:-====        :*%*+--------@@@@@@@@@@@
          .@@#       :=:   .::::::::-:.::::::-.::::::.::#.:-=-.:..::-.::-+:-=--===-=         -#++*+===-:#@@@@@@@@@@@@
         *@@*.    .  --.  .:::::::::-..::::.:::.::..:..-+:: :.......=-.::==--==-====-         .**++++++=*@@@@@@@@@@@@@@:
       =@@@==.   .: .=-.  ::::::.:::= .::::...::.-.....+::.  - :....:*::--==--=======-          -*++=+=++@@@@@@@@@@@@@@@@@@%-
     +@@@@::- . .:- :=-. .::::::.::=- .::......=.=.....+ :.  :  ... - -:-==+---==-=--*: .        .*++++=+%@@@@@@@@@@@@@@@
   :@@@@%.=.. : :--.-=:..:.::.:....-  ......... --:   ::.:.  .  :::.-  ----=#+====-==-*.           :*++=++@@@@@@@@@@@@@.
     +*#-- :.:: :-::==..::.:..:...:: .:....... . ::   :. :.      -::. ..:#=-=+-==-===-=+.+       ..  -+=++%#=-+=%@@@@#
        . ...::.--::==: ::........-:..=-   :  .   .   . .:.      :-*-    .:=-+====-==--=-+#       :.   +++++==+++++*@@*
          :.::.::-.-==-.=-:...--.: :.::-.  :            .:    :+--:.     ::.==+===---=-=+--%.      +@@=. :=*+++++++*++*
          .::::::::==---=-:.. =- .  ..: :..:  .:...  :  -. .+.   -*=:.+@@@@@@@@*====---=+*:**. .    =@@**%+:-+*%*++***+=
       . ...::::::-+=--+-=:--.+:.    ..  :.-.:::::. .:  :.*.  :-:+#@@%#++=%:-@##+===-==-=+--==+ ..   .###*+++**#@%#+*+++*=
       ..::::::::.*+--:=-----:=:-....::=:--=:....:..=. :.    ..+@@@*+==---#-=@*+*====-===+:-=*@% ::    *#*+*#+*++#%%%%##*+++-
       .::.:::::::%=--:-------: .     : -:-+#+-....= ..:     -*#::%+-:=+---:+**-+==-===-=-+-=@@@@ -#    =***#%#+*+#%==*+
      :.:::::::::-+=:---=-----. .      :. ::=..:..:   .       :   -=--:..:--+#-:-+=======-%==#@@@@:.@=   :#***%%#*+=#-==
      :-::-::::.:--*:---=-=---: . ..-+*#%#=-+:...:.                :+-....-+=::::#=======-*%-+@@@%@@-%%-  .#++*%%#*+#*+-
    . =-:::=:::::-:+.:--=-=--:- .=**+-:::+++%-..:.   .               ::..--:....:=#-=====-#@+=@@@%*%@%%@%-  -*+#%:*%++*=
      =:::---:------::-:==-=--+.      ....:  :.:.                     .   ......::*=-====-*@#-%@@%#*%%%%%%@*. +**- .*#**=
     +:::. :---=--=:=:-:==-==-:@.    .....:. ..:.                       ...::...--:*=====-+@@-*@%%*##%%*###+#*= +-  ::-:**
     ::-:   .:---.#:=.:-==-==-:%%    ....  ..:  :                              :=  ==-+==-*@@=*@%#**#%#****##*++**- .:     .
    .--      .:--:=:=-.-==-==-:%@+   ....   .:                                ::   :=--===#@@**%%**#*##***++**+=+*- ::
   :.         :----=.- -=-====-%@@:   ...   .      .                         .     :---==-@@@#%%%#*#*******+++***+# :
 .             -:--: .:-+--==-:%@@@                                              . #%:-===@@@#%##*##**+++#*+*+*+****-
                ::-:  *:%==----*+%@%   .                                        . #@%--+=*@%@%%##**#**+++%#*==+*++*+=
                -=$:-. #:+#+---:#%++%#.                      . .:. .:+          ..#@@@--**%%%%%###*+#++*++*--+*==+++-+.
                . =:: -==%@--=-=%**%%+                 =@+ .....:.:.:.         .*:@@%--%%@%%%####**#++*+++--:   .+*-==
                   :---+**%%---:@**%%#+     .      :@%%%::.:::::..:.:         .-::%%%-:@%%%%%###**#*+++=*+-::    :==:-=
               .    :=-+*##*#:-:**+*%**@:           =@#*:.::::::::::        .:...:@%%-+%%%%%###**+%*==+=%=:-.    ..    :.
               .     +*=+**%**-:=***##*+%%.        . .*%.:::::::::..       :. ....@%%=%%%#*#####+#%+===+:-:-.    .
                     .+-++**#+** +*-*++++%%%.    ..     --:.::.:::       =: .    .%%#+%%####*+@*++%+=-+. .:-
                      --++=**#*+*-++==+++%%%#@+..         .:::.        :=.  .    .%%%#*#*##*#+#=++#===:  .-
               .    . =-=+****+**+#:+==++#%%#%%%@%=. ..              :-:       .  %#%###%*##.:*+==#++-    :
                    .  :-=+=++***++#-:+++*++*#%%%%@@%=.. ..       :---.           #@@%@@@@=  :=  .+-+-
                .    . :.-===++**+==*+::+#++++*#%%%%%%%%-.     .*=:-:.            *%%%##*==+**#*+==*+=
                     :  -::====++*=+=+*==*=-=#**##%#%%%%%*+-:%#--:-. ..           .%#*=-==-*#*++==++-=#*:
                     :*::**=====+**==+=++*##*+++**##%%%%%%. :::.:. ..             .:=--===+@#*+++=+*+=-=+=*#=
                     #-=+==*=-++++#++==-++++*++++*#%%%%%%=-  .:.... .            .  -=--=+@#*#%@@%+==+=====+*+
                   ..*++==+**+:=*++%++++#++++++*+**#%%%%#-=. .:........              .@-=+++#%%@@%@=======++*@+
                .+-.-+*==*++#+-:=++*%+=**++++++*++**%%%%--=-.::..........            .: ==++*%@@%@+========+*#@@+
               -:--.=-*+*+++++=:.:-+*#+++*****=+*##%+#%==---::...........           :    .+%@@@%@#+======++*#%%@@#%=
              +::-:==--=*==**=#=:::-+#**+*+**++**%=.-++-:::--... ..  ....          :.     ..-@@@*++====++++*#%@@@%*=+.
              =---.=--:*+=+#*+=:-:--=++=**+++++*#+:=-.--:.:::..........           +        ..*%-+=-====+++*###@@@#+=+#*
              =----==-*+===@%:..-=---++##=+++***#-. .:=::...:..........         :=          :*:==-=====+++*%#%@@*++++##@*
             .+=-=*=+#*---==%:.:-=%+#+-:--+++*+*%:..  -::.............         :.          .--==-=======+*#*%@%+++==+##@#%+
             -:=##*+=-::-===+:.--+*#---::+*++++#+ ....-  .:.........  ..   . :+. .         =============+**#*++++===*%%#%###.
             :--*#@*+-::::-==-:-=#=.---:-+*==+#-......-:  ..........        :.            +============+*##**++====*%%%#**+=+
            .:---%=@*+-::--:-:.-*=:=:--=#++*@%-... . .-:.... ......       .:.           .=-===========+**+++===-===*#***+++=-:
            ..:-==+*#+*=:-::--.=+=::-=+*+%@+#@%.... ..-:.  .........     .-            .+============++========--===++**++==--
             .:----++%**-::  .+=+=++++++*%#+@@@%......-:.  .            =. .          .+-===-===-==++==--===------==+++====--:
              ..:--=*#%*+=   .=%##-:-+++*##+@@@@@.... -:.  .         ..-             -+==-======++*=======------==++======+*#*
               .::=-=#+#-  .::=#-:-:=++=+##*@@@@@@.. .::.  .         -:      .     .=+==-==+-==++=:=---=----========+**+=----:=
                .::--=+#=.:::-*=:::::++=+*#*%.#@@@@:..::.   .   .  .+           .=#*++++*+=====--=-=---=--=+**##*+=====-------:-
                 ..::-=*+::::=:.::::--===**+*. -@@@@:.::  ...  .  -.. .  .  .-%@@@*+*#*#*+====--=-:----*##*+==--==---======----:
                   ..:-:+:-:--:::--:::-+#*+++:   @@@@+:-  ..  .  +. ..   -@@@@@@@*@%*###*======*+-=-=%#=-=======-====-=======-:-+
                     ..:=::::::::::-:**++=-++.   .@@@@#= . .   :+    :#@@@@@@@@@%##%%%%#+++==#@%%@=**+==========-------=====-=+==
                       .  .:::::::--+==----+#++.  .@@@@@ .. ..:::+#%@%@@@@@@@#@%%%%%%@%*=+#@@@%@#%@=============------=====++++=+
                          ....  ..::=-:----+*=+**=++@@@@@:.-*@@%%%%%@@@@*: . .@@%%@%%@%**%@@@@@##@@*========--------=====+++*#*+==
                           .    ...::=:--==++=+++=+++%@@@@@@@%%@%@@#-      :%#%%%%@%#@@@@@@@%#@*@@+--===-----------======*##**=--
                                ...:.--:--=*+===++=++=#@@@@@%%%#*++=.     :%%%@@%%@@@@@@@@+@@#+*@@+===-----------====+++*##**+=-:
                                ....:+=:-==#++===+++===%@@%#*+==+++++++*##@@@%@@@@@@@@@**%##+=-%@#=-------------====+++*##*++=-:.
                                 ..:-+#===+#  .-:=+=*+*+#*+==+++++++++**%@@@@@@@@@@@*-@@#+=+==+@@=--------------===+++*##*+=-:.
**/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) scanf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 5e5 + 10;
struct Node {
	int l, r;
	
	// 如果只考虑当前结点以及子结点上的所有标记.当前区间和是多少
	LL sum;
	
	// 懒标记
	// 含义:所有被当前区间覆盖的或者说所有以当前区间为根结点的子树里面要给这整个子树都加上一个数add
	// 注意:这里的写法是不包含根结点本身的,也就是说这个区间本身是不需要+add的,没有所有祖先结点的标记
	// 给当前区间的所有儿子加上add.
	LL add;
}tr[N * 4];
int w[N];

void pushdown(int u) {
	auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
	if (root.add) {
		left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
		right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;
		root.add = 0;
	} 
}

void pushup(int u) {
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
} 

void build(int u, int l, int r) {
	if (l == r) tr[u] = {l, r, w[r], 0};
	else {
		tr[u] = {l, r};
		int mid = (l + r) / 2;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
		pushup(u);		
	}
}

void modify(int u, int l, int r, int d) {
	if (tr[u].l >= l && tr[u].r <= r) {
		tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
		tr[u].add += d;
	} 
	// 当前区间过大,我们需要裂开
	else {
		pushdown(u);
		int mid = (tr[u].l + tr[u].r) / 2;
		if (l <= mid) modify(u << 1, l, r, d);
		if (r > mid) modify(u << 1 | 1, l, r, d);
		pushup(u);
	}
}

LL query(int u, int l, int r) {
	if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
	
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) / 2;
	LL sum = 0;
	if (l <= mid) sum = query(u << 1, l, r);
	if (r > mid) sum += query(u << 1 | 1, l, r);
	return sum;
}

void solve() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    fore (i, 1, n) scanf("%d", &w[i]);
    
    build(1, 1, n);
    
    char op[2];
    int l, r, d;
    
    while (m--) {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C'){
        	scanf("%d", &d);
        	modify(1, l, r, d);
        } else {
        	printf("%lld\n", query(1, l, r));
        }
    }
}
int main()
{
    // IOS;
    int _ = 1;
    // cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}