树状数组详解
https://blog.csdn.net/sjystone/article/details/115396746

线段树详解
https://blog.csdn.net/sjystone/article/details/115398593

1.树状数组做法

区间加，区间求和  
区间求和
求a1 + a2 +...+ ax  (ax = b1 + b2 +...+ bx)
    朴素法
    for ( int i = 1; i <= x; i ++ )
        for ( int j =1; j <= i; j ++ )  
            res += b[j];

    优化法
                      2)
1)                    b1 b2 b3 b4 ... bx    注：在没有b的第0行也要补，补完后是x+1行
b1                    b1 b2 b3 b4 ... bx
b1 b2                 b1 b2 b3 b4 ... bx
b1 b2 b3              b1 b2 b3 b4 ... bx
...                   ...
b1 b2 b3 b4 ... bx    b1 b2 b3 b4 ... bx

2)的求和：(b1 + b2 + ... + bx) * (x + 1)
1)的求和：(b1 + b2 + ... + bx) * (x + 1) - (b1 + 2*b2 + ... + x*bx)
    -> 2)减去i*b的前缀和
    -> 用tr1维护bi的前缀和，tr2维护i*bi的前缀和
    -> sum(tr1, x) * (x + 1) - sum(tr2, x)

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
LL tr1[N], tr2[N];
int a[N], n, m;

int lowbit(int x)
{
    return x & -x;
}

void add(LL tr[], int x, LL c)
{
    for ( int i = x; i <= n; i += lowbit(i) ) tr[i] += c;
}

LL sum(LL tr[], int x)
{
    LL res = 0;
    for ( int i = x; i; i -= lowbit(i) ) res += tr[i];
    return res;
}

LL prefix_sum(int x)
{
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main()
{
    cin >> n >> m;
    for ( int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for ( int i = 1; i <= n; i ++ )
    {
        add(tr1, i, a[i] - a[i - 1]);
        add(tr2, i, (LL)(a[i] - a[i - 1]) * i); //可能会爆int
    }

    while ( m -- )
    {
        char op[2];
        int l, r, d;
        scanf("%s%d%d", op, &l, &r);
        if ( *op == 'C' ) 
        {
            scanf("%d", &d);
            add(tr1, l, d), add(tr2, l, l * d);
            add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
        }
        else printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
    }
    return 0;
}

2.线段树做法

1.区间修改，区间查询

储存信息：
    sum - 如果考虑当前节点和子节点上的所有标记，当前的区间和（没有考虑祖先节点的标记）
    add - 给当前区间的所有儿子（不包括自己），加上add
    l, r

add懒标记 -> 一当前节点为跟的子树中的每一个节点加上add，不包含当前区间自己
从上往下递归时，将add标记传到子区间，并删去当前节点的标记 -> pushdown
eg：
    跟节点为root
    left.add += root.add
    left.sum += (left.r - left.l + 1) * root.add
    right.add += root.add
    right.sum += (right.r - right.l + 1) * root.add
    root.add = 0; 
在修改操作，区间分裂时，要先把标记往下传
在查询操作时，要先把标记往下传

pushup放到build和modify最后，pushdown放到modify和query前面

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long LL;
const int N = 100010;
int n, m, w[N];
struct Node{
    int l ,r;
    LL sum, add;
} tr[4 * N];

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

void pushdown(int u)
{
    Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if ( root.add ) 
    {
        left.add += root.add;
        right.add += root.add;
        left.sum += (LL)(left.r - left.l + 1) * root.add;
        right.sum += (LL)(right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;
    if ( l == r ) tr[u].sum = w[l], tr[u].add = 0;
    else
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d)
{
    if ( tr[u].l >= l && tr[u].r <= r )
    {
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if ( mid >= l ) modify(u << 1, l, r, d);
        if ( mid < r ) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if ( tr[u].l >= l && tr[u].r <= r ) return tr[u].sum;
    else
    {
        pushdown(u);
        LL sum = 0;
        int mid = tr[u].l + tr[u].r >> 1;
        if ( mid >= l ) sum = query(u << 1, l, r);
        if ( mid < r ) sum += query(u << 1 | 1, l, r);
        return sum;
    }
}

int main()
{
    cin >> n >> m;
    for ( int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);
    char op[2];
    int l, r, d;
    while ( m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if ( *op == 'C' ) 
        {
            scanf("%d", &d);
            modify(1, l, r, d);
        }
        else printf("%lld\n", query(1, l, r));
    }
    return 0;
}