Description
给出了一个序列，你需要处理如下两种询问。
"C a b c"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。
"Q a b" 询问[a, b]区间中所有值的和。
Input
第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000.
第二行包含n个整数，表示初始的序列A (-1000000000 ≤ Ai ≤ 1000000000)。
接下来Q行询问，格式如题目描述。
Output
对于每一个Q开头的询问，你需要输出相应的答案，每个答案一行。
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 此题和上两题相似，但是区间更新和区间查询，我用了树状数组，zkw线段树还不会区间更新；直接上代码：
import java.io.BufferedInputStream;
import java.util.Scanner; public class Main {
static int n;
static long[] arr = new long[1000001];
static long sun;static long c1[] = new long[100005];
static long c2[] = new long[100005];static String order; public static void main(String[] args) throws Exception {
Scanner s = new Scanner(new BufferedInputStream(System.in));
n = s.nextInt();
int m = s.nextInt(),k, first, second;
for (int i = 1; i <= n; i++) {
arr[i] = s.nextLong();
arr[i] += arr[i - 1];
}
while (m-- != 0) {
order = s.next(); if (order.equals("Q")) { //区间查询
first = s.nextInt();
second = s.nextInt();
sun = arr[second]-arr[first-1]+(second+1)*query(second, c1)-first*query(first-1, c1)-query(second, c2)+query(first-1, c2);
System.out.println(sun);
} else { //区间更新
first = s.nextInt();
second = s.nextInt();
k = s .nextInt();
Add(first,k,c1);
Add(second+1,-k,c1);
Add(first,k*first,c2);
Add(second+1,-k*(second+1),c2); }
}
s.close();
}
static long query(int k, long c[])
{
long ans=0;
while(k>0) {
ans += c[k];
k -= lowbit(k);
}
return ans;
} static void Add(int k, int change, long c[])
{
while(k <= n) {
c[k] += change;
k += lowbit(k);
}
}
static int lowbit(int x) {
return -x & x;
}
}