# POJ 3468 A Simple Problem with Integers（线段树区间更新）

xiaoxiao2021-03-01  48

# A Simple Problem with Integers

Time Limit: 5000MS

Memory Limit: 131072K

Total Submissions: 142569

Accepted: 44259

Case Time Limit: 2000MS

Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

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

Sample Output

4 55 9 15

Hint

The sums may exceed the range of 32-bit integers.

Source

POJ Monthly--2007.11.25, Yang Yi

------------------------------------------------------------

------------------------------------------------------------

------------------------------------------------------------

#include<cstdio> const int NMAX = 100005; long long a[NMAX]; // 输入数组 long long val[4*NMAX]; // 线段树（值） long long mark[4*NMAX]; // 线段树（懒标记） void build(int root, int lp, int rp) // 根据a[lp:rp]建树 { mark[root] = 0; // 建树时懒标记清零 if (lp == rp) { val[root] = a[lp]; return; } int mid = (lp + rp)/ 2; build(2*root+1, lp, mid); build(2*root+2, mid+1, rp); val[root] = val[2*root+1] + val[2*root+2]; } void push_down(int root, int tl, int tr) // 懒标记向下传递 { if (mark[root] != 0) { int mid = (tl + tr) / 2; long long tmp = mark[root]; mark[2*root+1] += tmp; mark[2*root+2] += tmp; val[2*root+1] += tmp * (mid - tl + 1); // 用懒标记修改左子树 val[2*root+2] += tmp * (tr - mid); // 用懒标记修改右子树 mark[root] = 0; // 清零父节点的懒标记（避免重复计算） } } long long query(int root, int tl, int tr, int ql, int qr) // 查询区间[ql, qr]的和 { if (tl > qr || tr < ql) { return 0; } else if (ql <= tl && tr <= qr) { return val[root]; } push_down(root, tl, tr); // 递归过程中将懒标记向下传递 int mid = (tl + tr) / 2; return query(2*root+1, tl, mid, ql, qr) + query(2*root+2, mid+1, tr, ql, qr); } void update(int root, int tl, int tr, int ql, int qr, long long addi) // 区间[ql,qr]中的每一个元素各自增加addi { if (tl > qr || tr < ql) { return; } else if (ql <= tl && tr <= qr) { val[root] += addi * (tr - tl + 1); mark[root] += addi; // 修改懒标记，待有更小区间的查询或修改时向下传递 return; } push_down(root, tl, tr); // 递归过程中将懒标记向下传递 int mid = (tl + tr) / 2; update(2*root+1, tl, mid, ql, qr, addi); update(2*root+2, mid+1, tr, ql, qr, addi); val[root] = val[2*root+1] + val[2*root+2]; // 根据左右子树修改后的值回溯更新父亲节点 } int main() { #ifndef ONLINE_JUDGE freopen("3468.txt", "r", stdin); #endif int N, Q, i, ql, qr; long long addi; char inst; scanf("%d%d", &N, &Q); for (i=0; i<N; i++) { scanf("%lld", a+i); } build(0, 0, N-1); for (i=0; i<Q; i++) { getchar(); // 读入回车 scanf("%c%d%d", &inst, &ql, &qr); ql --; qr --; if (inst == 'C') { scanf("%lld", &addi); update(0, 0, N-1, ql, qr, addi); } else { printf("%lld\n", query(0, 0, N-1, ql, qr)); } } return 0; }