题目来源：http://poj.org/problem?id=3468

问题描述

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

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

题意

线段树区间更新和区间查询的模板题。

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

思路

线段树区间更新引入了“懒标记”，目的是在第一次update的时候不用修改每一个元素的值，只需要整体区间修改即可；以后如果query或update需要用到更小的区间，则在query或update时逐层push_down懒标记并利用懒标记修改各层的节点值。所以相比于只有单点更新的线段树，区间更新多了push_down函数，build函数中多了对于懒标记的预置零操作，query和update函数中递归部分加入push_down，update到目标节点时除了修改节点值还要修改懒标记。由于一棵线段树上同时可以存在多个懒标记，故修改懒标记时用“+=”而非“=”. 详见“代码”部分。

本题需要注意的是所有涉及到线段树节点求值和懒标记的部分都要用long long，包括区间修改的增值也要用long long读入(scanf(“%lld”, &addi)).

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

代码

#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; }