UOJ Logo LFYZ Online Judge

LFYZOJ

#65. 【模板】线段树/分块

统计

本题可以使用树状数组、线段树、分块做。分块对应的是 hzwer 分块四。

问题描述

给你一个长度为 $n$ 的数列,要求你完成 $m$ 个操作,操作分为两类:

  • C $\ i\ j\ k$,表示把位于 $[i,j]$ 之间的数加上 $k$。
  • Q $i\ j$,输出位于 $[i,j]$ 之间的数的和。

输入格式

第一行两个整数 $n,m$。

下来 $m$ 行,每行一个操作。

输出格式

对于每个 Q,输出你的答案并换行。

样例一

input

10 10
-747500228 165829336 304700715 84127875 -838231738 -731889283 343644199 916295544 -325839727 -588243755
C 8 10 -9017
Q 5 7
Q 1 5
Q 7 10
Q 1 7
Q 1 6
C 3 9 -7176
Q 6 7
C 6 8 -3184
C 5 10 2491

output

-1226476822
-1031074040
345829210
-1419319124
-1762963323
-388259436

数据范围与约定

对于 $100\%$ 的数据,$1 \leq n \leq m \leq 100000$,数列中的数初始都 $\in [-10^9,10^9]$,$1 \leq i \leq j \leq n$,$-10000 \leq k \leq 10000$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$