【线段树】【模板】讲解 + 例题1 HDU - 1754 I Hate It （点修改分数）+ 例题二 POJ - 3468 A Simple Problem with Integers（区间加值）

---

讲解

1、线段树的构成

• 线段树是一种二叉搜索树，它从上至下逐步将一个大区间划分成一些更小的单元区间，每个区间对应线段树中的一个节点
• 树中的每个节点代表着一段区间[L,R]，每个节点（除叶子节点）的左儿子代表的区间为[L,mid],右儿子则为[mid+1,r]。可以发现对于一个节点来说，左右儿子所代表的区间加起来正好为当前节点的区间
• 叶子节点的所代表的长度为1，根节点代表的区间为整个序列区间
• 长度范围为[1,L] 的一棵线段树的深度为log (L) + 1。

2、线段树的性质

• 从根出发，到任意一个节点的距离为logn
• 对于任意一个区间[L,R]，我们可以把它划分为logn个存在于线段树中的区间，比如[5,8]我们可以划分为[5,5]和[6,8] 。
• 对于此线段树维护的序列中的每个元素来说，他都被包含在logn个存在于线段树的区间中，而且这些区间构成一条从根到叶子的路径，同时这个叶子必然代表的是这个元素本身。例如“5”这个元素被包含在[1,10]、[1,5]、[4,5]、[5,5]这几个区间内。

3、线段树的用途

• 四大类问题： 区间询问、 区间修改、 点修改、 点询问
• 线段树作为一种数据结构，自然是用来维护信息的。由于它每个节点所代表的是一个区间，所以自然每个节点所维护的就是它所代表的区间的信息。而具体是维护什么信息，就要根据题目要求来决定。比如维护区间最值，区间和等等。
• 对于一种数据结构来说，所有的修改操作都可以归结为“维护数据结构的正确性”。可以用类似于数学归纳法的思维方式来思考：首先保证初始时数据结构里的信息都是正确的，再保证每次修改之后数据结构的信息也是正确的就行了。所以“修改”其实就是使得数据结构内的信息是正确的
• 举例：区间最大值维护
  
  
  • 我们考虑一个叶子节点。由图可知叶子代表的区间长度为1，假如是[5,5]，那显然的，[5,5]这个区间的最大值自然就是A[5]本身了
  • 我们再往上走一层。对于一个非叶子节点来说，它所代表的区间被左右儿子几乎均等划分，而刚才叶子节点的最大值已经求出来了，所以对于这一层的节点来说，它的最大值只需要把左右儿子的最大值取个max即可。
  • 再往上走一层，发现他的儿子信息也是正确的，所以合并过了就好了。再往上，再往上……构建好了。

4、点修改、点询问

• 4.1 点修改： 现在假如我们要修改[8]这个位置，从图中可以看到，8只属于[1,10]、[6,10]、[6,8]、[8,8]这几个区间，所以我们只需要把这几个点的信息维护一下就OK了
• 4.2 点询问: 只需要走到[8,8]这个位置，拿到值再回来就行了
• 可以发现，这两个操作都是logn的复杂度（走的步数不会超过树的深度）
  

5、区间询问

• 任意一个区间，都可以被划分为logn个存在于线段树中的区间。
• 假如现在需要询问[3,7]这个区间的最大值，则可以发现，[3,7]被划分为[3,3]、[4,5]、[6,7]三个区间
  所以剩下的也就很简单啦，我们找到这三个区间，把这三个区间的最大值都拿出来取个最大值就行啦
• 可以发现我们最多走logn条路径，每条路径深度最多logn，所以复杂度的上界是O((logn)^2)的。但实际上其实很难达到这个上界，一般都认为是 O（logn）的

6、区间修改

• 考虑现在有一个[6,8]的修改。我们先考虑修改过后会对哪些位置产生影响：和[6,8]这个区间有交集的区间都有被影响的可能！所以为了维护数据结构的正确性，我们需要把所有可能被影响的区间都去访问一遍。以[6,8]为例，[6,8]子树以及[6,8]的父亲都会被它影响。那如果是[1,9]被修改呢？你会发现全树所有节点都会被影响。。复杂度BOOMMMMM~
• 解决的办法称为lazy标记，对于一个[6,9]的修改，我们只找到它被分割的区间[6,8]、[9,9]，同时把这两个区间以及它们的祖先的信息维护一下，他们的儿子则不考虑。然后给这两个区间打上lazy标记所谓的打标记，就是改变这个节点维护的lazy的值，这样做的复杂度和区间询问的复杂度是一样的。
• 大家可能会有疑问。因为我们这样只更新了一部分被影响的节点，这样导致的结果自然就是有一些区间维护的信息并不是正确的。这是否和确保正确性相冲突呢？确实是有冲突的。但是这个冲突并不重要，或者说不影响我们之后的操作。
• 一个数据结构无非两种操作：修改和询问。我们只要保证询问的时候，拿到的信息都是正确的就行了。那么我们每一次询问到一个节点的时候，如果发现它有lazy tag，那么就把lazy tag下传，然后将该节点的lazy tag清空，确保每一次我们访问的节点的信息正确即可。那么这样修改一整个区间的操作其实就被我们分散在每一次查询中了，因为反正查询也要进行这些步骤，也要访问到某一个深度的节点，那么我们就在这个过程中同时进行信息的维护即可。

7、权值线段树

• 权值线段树：把线段树节点下标设成权值的线段树（可以类比权值树状数组）。
• 如对于位置i，它的权值是a[i]，某个问题要求每个位置之前的权值在a[i]-w[i]到a[i]之间点的个数。
• 此时每次插入a[i]前，查询一下sum（a[i]-w[i],a[i]），即为ans[i]
• 然后再插入一次a[i]，add(a[i],1)

8、总结 - 线段树类问题的思考步骤

• 第一：
  思考这个题目是否是一个区间相关的问题，能否使用线段树

• 第二：
  考虑我们需要的信息有哪些。比如题目要求询问区间最大值，那自然我们需要的信息就是“最大值”了。但是有时候（其实是大部分时候）没办法直接得到答案，所以我们需要维护一些其他信息来计算得到答案。

• 第三：
  思考叶子节点的信息是什么。叶子所代表的长度为1，所以这个点所维护的信息往往是很容易求得的，一般可以直接赋值

• 第四：
  思考非叶子的节点的信息如何从左右儿子合并过来（pushup(函数)），之所以有这个过程，是因为在维护u这个点的信息时，u的左右儿子的信息都已经完成了维护，都是正确的，所以我们只需要通过u的左右儿子的信息得到u的信息。具体到例题里就是从左右儿子的最大值中取一个最大的得到当前区间的信息。

• 第五：
  思考当u节点的标记下传时，这个标记对左右儿子的影响。可以理解为现在有一个修改对左右儿子操作。

9、模板一：数组类

k<<1,k<<1|1就是k*2和k*2+1这两个点，位运算常数更小，让常数优化成为一种习惯(避免碰到卡常题)

9.1 点修改 区间询问（以最大值为例）

int a[maxn];//原始数据
int maxx[maxn<<2];//线段树中维护的信息：区间最大值


void pushup(int rt)//向上更新（父节点由左右子树更新）
{
    maxx[rt] = max(maxx[rt<<1], maxx[rt<<1|1]);
}

void build(int l, int r, int rt)//建树
{
    if(l == r)//叶子节点直接得到信息
    {
        maxx[rt] = a[l];
        return ;
    }
    int m = (r + l)>>1;
    //建左右子树
    build(l, m, rt<<1);
    build(m + 1, r, rt<<1|1);
    pushup(rt);//更新父节点信息
}

//点修改
void update(int d, int x, int l, int r, int rt)//将d改为x
{
    if(l == r)
    {
        maxx[rt] = x;
        return ;
    }
    int m = (l + r)>>1;
    if(d <= m)//更新节点在当前节点的左子树
        update(d, x, l, m, rt<<1);
    else//更新节点在当前节点的右子树
        update(d, x, m + 1, r, rt<<1|1);
    pushup(rt);
}

//区间询问
int query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R)//如果询问区间大于当前节点管辖区间，返回该区间全部值
        return maxx[rt];
    int m = (l + r)>>1;
    if(R <= m)//询问区间在当前节点的左子树
        return query(L, R, l, m, rt<<1);
    else if(L > m)//询问区间在当前节点的右子树
        return query(L, R, m + 1, r, rt<<1|1);
    else//询问区间，跨越当前节点的左右子树，分别查询后综合信息。
        return max(query(L, R, l, m, rt<<1), query(L, R, m + 1, r, rt<<1|1));
}

9.2 区间修改、区间询问 （以区间和为例）

long long sum[maxn << 2], a[maxn], add[maxn << 2];//add为lazy tag

void pushup(int rt)//向上更新
{
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void pushdown(int rt, int ln, int rn)//向下更新标记
{
    if(add[rt])
    {
        add[rt << 1] += add[rt];//标记下传
        add[rt << 1 | 1] += add[rt];
        sum[rt << 1] += ln * add[rt];//更新左右子树维护的信息
        sum[rt << 1 | 1] += rn * add[rt];
        add[rt] = 0;//清空当前节点标记
    }
}

void build(int l, int r, int rt)//建树
{
    if(l == r)
    {
        sum[rt] = a[l];
        return ;
    }
    int m = (r + l) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    pushup(rt);//更新当前节点信息
}


//区间修改
void update(int L, int R, int c, int l, int r, int rt)
{
    if(L <= l && r <= R)//如果修改区间大于当前节点的区间，那么当前节点区间的所有值都应该被修改
    {
        sum[rt] += (r - l + 1) * c;//sum加上该区间 数的个数乘以每个数增加的值
        add[rt] += c;//lazy tag 表示该节点以下的值需要被修改多少
        return ;
    }
    pushdown(rt, m - l + 1, r - m);//标记下传
    int m = (l + r) >> 1;
    if(L <= m)//更新左子树部分
        update(L, R, c, l, m, rt << 1);
    if(R > m)//更新右子树部分
        update(L, R, c, m + 1, r, rt << 1 | 1);
    pushup(rt);//更新当前节点
}


//区间询问
long long query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R)//如果询问区间大于当前节点的区间，返回该区间的值
    {
        return sum[rt];
    }
    pushdown(rt, m - l + 1, r - m);//标记下传
    int m = (l + r) >> 1;
    long long Sum = 0;
    if(L <= m)//查询左子树部分的值
        Sum += query(L, R, l, m, rt << 1);
    if(R > m)//查询右子树部分的值
        Sum += query(L, R, m + 1, r, rt << 1 | 1);
    return Sum;//返回累加和
}

10、模板二：结构体类

10.1 点修改 区间查询（以最大值为例）

struct node
{
    int l, r, maxnum;
}tree[maxn<<2];


void push_up(int k)
{
    tree[k].maxnum = max(tree[k<<1].maxnum, tree[k<<1|1].maxnum);
}

void build(int k, int l, int r)
{
    tree[k].l = l;
    tree[k].r = r;
    if(l == r)
    {
        tree[k].maxnum = a[l];
        return ;
    }
    int mid = (l + r)>>1;
    build(k<<1, l, mid);
    build(k<<1|1, mid + 1, r);
    push_up(k);
}

void update(int k, int d, int x)
{
    if(tree[k].l == tree[k].r && tree[k].l == d)
    {
        tree[k].maxnum = x;
        return ;
    }
    int mid = (tree[k].l + tree[k].r)>>1;
    if(d >= tree[k].l && d <= mid)
        update(k<<1, d, x);
    else
        update(k<<1|1, d, x);
    push_up(k);
}

int query(int k, int l, int r)
{
    int maxnum;
    if(tree[k].l == l && tree[k].r == r)
        return tree[k].maxnum;
    int mid = (tree[k].l + tree[k].r)>>1;
    if(r <= mid)
        maxnum = query(k<<1, l, r);
    else if(l > mid)
        maxnum = query(k<<1|1, l, r);
    else
        maxnum = max(query(k<<1, l, mid), query(k<<1|1, mid + 1, r));
    return maxnum;
}

10.2 区间修改 区间查询（以区间和为例）

int a[maxn];
struct node
{
    int l, r;
    LL sum, lazy;
}tree[maxn<<2];

void push_up(int k)
{
    tree[k].sum = tree[k<<1].sum + tree[k<<1|1].sum;
}

void push_down(int k)
{
    if(tree[k].l != tree[k].r)
    {
        tree[k<<1].sum += (tree[k<<1].r - tree[k<<1].l + 1) * tree[k].lazy;
        tree[k<<1|1].sum += (tree[k<<1|1].r - tree[k<<1|1].l + 1) * tree[k].lazy;
        tree[k<<1].lazy += tree[k].lazy;
        tree[k<<1|1].lazy += tree[k].lazy;
    }
    tree[k].lazy = 0;
}

void build(int k, int l, int r)
{
    tree[k].l = l;
    tree[k].r = r;
    if(l == r)
    {
        tree[k].sum = a[l];
        return ;
    }
    int mid = (l + r)>>1;
    build(k<<1, l, mid);
    build(k<<1|1, mid + 1, r);
    push_up(k);
}

void update(int k, int l, int r, int x)
{
    if(tree[k].lazy)
        push_down(k);
    tree[k].sum += (r - l + 1) * x;
    if(tree[k].l == l && tree[k].r == r)
    {
        tree[k].lazy += x;
        return ;
    }
    int mid = (tree[k].l + tree[k].r)>>1;
    if(r <= mid)
        update(k<<1, l, r, x);
    else if(l > mid)
        update(k<<1|1, l, r, x);
    else
    {
        update(k<<1, l, mid, x);
        update(k<<1|1, mid + 1, r, x);
    }
    push_up(k);
}

LL query(int k, int l, int r)
{
    LL sum;
    if(tree[k].lazy)
        push_down(k);
    if(tree[k].l == l && tree[k].r == r)
        return tree[k].sum;
    int mid = (tree[k].l + tree[k].r)>>1;
    if(r <= mid)
        sum = query(k<<1, l, r);
    else if(l > mid)
        sum = query(k<<1|1, l, r);
    else
        sum = query(k<<1, l, mid) + query(k<<1|1, mid + 1, r);
    return sum;
}

---

例题1 HDU - 1754 I Hate It

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0 < N <= 200000,0 < M < 5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ，和两个正整数A，B。
当C为’Q’的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为’U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output
对于每一次询问操作，在一行里面输出最高成绩。

Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

Sample Output
5
6
5
9

Hint
Huge input,the C function scanf() will work better than cin

AC代码
数组类

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <set>
#define maxn 200005

using namespace std;

int maxx[maxn<<2], add[maxn<<2];
int a[maxn];

void pushup(int rt)
{
    maxx[rt] = max(maxx[rt<<1], maxx[rt<<1|1]);
}

void build(int l, int r, int rt)
{
    if(l == r)
    {
        maxx[rt] = a[l];
        return ;
    }
    int m = (r + l)>>1;
    build(l, m, rt<<1);
    build(m + 1, r, rt<<1|1);
    pushup(rt);
}

void update(int L, int c, int l, int r, int rt)
{
    if(l == r)
    {
        maxx[rt] = c;
        return ;
    }
    int m = (l + r)>>1;
    if(L <= m)
        update(L, c, l, m, rt<<1);
    else
        update(L, c, m + 1, r, rt<<1|1);
    pushup(rt);
}

int query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R)
        return maxx[rt];
    int m = (l + r)>>1;
    if(R <= m)
        return query(L, R, l, m, rt<<1);
    else if(L > m)
        return query(L, R, m + 1, r, rt<<1|1);
    else
        return max(query(L, R, l, m, rt<<1), query(L, R, m + 1, r, rt<<1|1));
}

int main()
{
    int N, M;
    while(~scanf("%d%d", &N, &M))
    {
        for(int i = 1; i <= N; i++)
            scanf("%d", &a[i]);
        build(1, N, 1);
        char c[2];
        int A, B;
        for(int i = 1; i <= M; i++)
        {
            scanf("%s%d%d", c, &A, &B);
            if(strchr(c, 'Q'))
                printf("%d\n", query(A, B, 1, N, 1));
            else
                update(A, B, 1, N, 1);
        }
    }
    return 0;
}

结构体类

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#define clr(x, y)  memset(x, y, sizeof(x))
#define INF 0x3f3f3f3f
#define EPS 1e-8

using namespace std;
const int maxn = 200005;
int a[maxn];

struct node
{
    int l, r, maxnum;
}tree[maxn<<2];


void push_up(int k)
{
    tree[k].maxnum = max(tree[k<<1].maxnum, tree[k<<1|1].maxnum);
}

void build(int k, int l, int r)
{
    tree[k].l = l;
    tree[k].r = r;
    if(l == r)
    {
        tree[k].maxnum = a[l];
        return ;
    }
    int mid = (l + r)>>1;
    build(k<<1, l, mid);
    build(k<<1|1, mid + 1, r);
    push_up(k);
}

void update(int k, int d, int x)
{
    if(tree[k].l == tree[k].r && tree[k].l == d)
    {
        tree[k].maxnum = x;
        return ;
    }
    int mid = (tree[k].l + tree[k].r)>>1;
    if(d >= tree[k].l && d <= mid)
        update(k<<1, d, x);
    else
        update(k<<1|1, d, x);
    push_up(k);
}

int query(int k, int l, int r)
{
    int maxnum;
    if(tree[k].l == l && tree[k].r == r)
        return tree[k].maxnum;
    int mid = (tree[k].l + tree[k].r)>>1;
    if(r <= mid)
        maxnum = query(k<<1, l, r);
    else if(l > mid)
        maxnum = query(k<<1|1, l, r);
    else
        maxnum = max(query(k<<1, l, mid), query(k<<1|1, mid + 1, r));
    return maxnum;
}

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        clr(tree, 0);
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        build(1, 1, n);
        int A, B;
        char op[2];
        for(int i = 1; i <= m; i++)
        {
            scanf("%s%d%d", op, &A, &B);
            if(op[0] == 'U')
                update(1, A, B);
            else
                printf("%d\n", query(1, A, B));
        }
    }
    return 0;
}

---

例题二 POJ - 3468 A Simple Problem with Integers

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.

AC代码：
数组类

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 100005

using namespace std;

long long sum[maxn<<2], a[maxn], add[maxn<<2];

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

void build(int l, int r, int rt)
{
    if(l == r)
    {
        sum[rt] = a[l];
        return ;
    }
    int m = (r + l)>>1;
    build(l, m, rt<<1);
    build(m + 1, r, rt<<1|1);
    pushup(rt);
}

void pushdown(int rt, int ln, int rn)
{
    if(add[rt])
    {
        add[rt<<1] += add[rt];
        add[rt<<1|1] += add[rt];
        sum[rt<<1] += ln * add[rt];
        sum[rt<<1|1] += rn * add[rt];
        add[rt] = 0;
    }
}

void update(int L, int R, int c, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        sum[rt] += (r - l + 1) * c;
        add[rt] += c;
        return ;
    }
    int m = (l + r)>>1;
    pushdown(rt, m - l + 1, r - m);
    if(L <= m)
        update(L, R, c, l, m, rt<<1);
    if(R > m)
        update(L, R, c, m + 1, r, rt<<1|1);
    pushup(rt);
}



long long query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        return sum[rt];
    }
    int m = (l + r)>>1;
    pushdown(rt, m - l + 1, r - m);
    long long Sum = 0;
    if(L <= m)
        Sum += query(L, R, l, m, rt<<1);
    if(R > m)
        Sum += query(L, R, m + 1, r, rt<<1|1);
    return Sum;
}

int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++)
        scanf("%lld", &a[i]);
    build(1, N, 1);
    memset(add, 0, sizeof(add));
    char c[2];
    int A, B, C;
    for(int i = 1; i <= M; i++)
    {
        scanf("%s%d%d", c, &A, &B);
        if(strchr(c, 'Q'))
            printf("%lld\n", query(A, B, 1, N, 1));
        else
        {
            scanf("%d", &C);
            update(A, B, C, 1, N, 1);
        }
    }
    return 0;
}

结构体类

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#define clr(x, y)  memset(x, y, sizeof(x))
#define INF 0x3f3f3f3f
#define EPS 1e-8

using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
int a[maxn];
struct node
{
    int l, r;
    LL sum, lazy;
}tree[maxn<<2];

void push_up(int k)
{
    tree[k].sum = tree[k<<1].sum + tree[k<<1|1].sum;
}

void push_down(int k)
{
    if(tree[k].l != tree[k].r)
    {
        tree[k<<1].sum += (tree[k<<1].r - tree[k<<1].l + 1) * tree[k].lazy;
        tree[k<<1|1].sum += (tree[k<<1|1].r - tree[k<<1|1].l + 1) * tree[k].lazy;
        tree[k<<1].lazy += tree[k].lazy;
        tree[k<<1|1].lazy += tree[k].lazy;
    }
    tree[k].lazy = 0;
}

void build(int k, int l, int r)
{
    tree[k].l = l;
    tree[k].r = r;
    if(l == r)
    {
        tree[k].sum = a[l];
        return ;
    }
    int mid = (l + r)>>1;
    build(k<<1, l, mid);
    build(k<<1|1, mid + 1, r);
    push_up(k);
}

void update(int k, int l, int r, int x)
{
    if(tree[k].lazy)
        push_down(k);
    tree[k].sum += (r - l + 1) * x;
    if(tree[k].l == l && tree[k].r == r)
    {
        tree[k].lazy += x;
        return ;
    }
    int mid = (tree[k].l + tree[k].r)>>1;
    if(r <= mid)
        update(k<<1, l, r, x);
    else if(l > mid)
        update(k<<1|1, l, r, x);
    else
    {
        update(k<<1, l, mid, x);
        update(k<<1|1, mid + 1, r, x);
    }
    push_up(k);
}

LL query(int k, int l, int r)
{
    LL sum;
    if(tree[k].lazy)
        push_down(k);
    if(tree[k].l == l && tree[k].r == r)
        return tree[k].sum;
    int mid = (tree[k].l + tree[k].r)>>1;
    if(r <= mid)
        sum = query(k<<1, l, r);
    else if(l > mid)
        sum = query(k<<1|1, l, r);
    else
        sum = query(k<<1, l, mid) + query(k<<1|1, mid + 1, r);
    return sum;
}

int main()
{
    int n, q;
    while(~scanf("%d%d", &n, &q))
    {
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        clr(tree, 0);
        build(1, 1, n);
        char op[2];
        int A, B, C;
        for(int i = 1; i <= q; i++)
        {
            scanf("%s%d%d", op, &A, &B);
            if(op[0] == 'C')
            {
                scanf("%d", &C);
                update(1, A, B, C);
            }
            else
                printf("%lld\n", query(1, A, B));
        }
    }
    return 0;
}