Algorithm

线段树-两种操作

线段树是一种二叉树结构，能够在lg(n)的复杂度下完成一些计算。
最长见的就是数列求和之类的，而且还能够支持单点修改甚至是区间修改。

线段树的精髓在于懒惰标记，也就是说，在更新的时候，不更新全部子节点，只会打一个标记。

比如说一段区间要加一个值，它不会在每个叶子节点加上相应数值，而是在覆盖需要修改的子节点的区间上加一个tag要加多少，相应的因为要保证上层计算无误，所以要根据自己的孩子数更新自己的sum值。
如果下次要更新这段覆盖的区间的子区间，可以把相应的标记下放。

线段树支持两种操作其实也比较简单，就是考虑两种操作的优先级，根据优先级判断相关节点应该怎么操作。

下面是一个乘和加两种操作的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/*
Sample Input:
6 3
add 0 2 1
mul 2 4 3
sum 0 3
6 3
sum 0 5
mul 0 5 4
sum 0 5
Sample Output:
21
15
60
先输入两个数n和m,代表数组为0,1,2,3,...,n-1,要进行m种操作
下m行,每行开始是一个字符串,代表操作。
add 0 2 1
代表位置为0,1,2的数 都加1
mul 2 4 3
代表位置为2,3,4的数 都乘3
sum 0 3
代表求0,1,2,3的和
*/
/***********************************************\
 |Author: YMC
 |Created Time: 2015-1-20 12:14:28
 |File Name: Multiply_and_Add_zjut1101.cpp
 |Description: 
\***********************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define L(rt) (rt<<1)
#define R(rt) (rt<<1|1)
#define mset(l,n) memset(l,n,sizeof(l))
#define rep(i,n) for(int i=0;i<n;++i)
#define maxx(a) memset(a, 0x3f, sizeof(a))
#define zero(a) memset(a, 0, sizeof(a))
#define srep(i,n) for(i = 1;i <= n;i ++)
#define MP make_pair
const int inf=0x3f3f3f3f ;
const double eps=1e-8 ;
const double pi=acos (-1.0);
typedef long long ll;
using namespace std;
const int maxn = 100005;
const int mod = 1000000007;
struct Tree{
    ll sum;
    int l,r;
    ll add,mul;
}tree[maxn << 2];
char op[10];
int n,m;
int a,b;
ll c;
void pushup(int rt) {
    tree[rt].sum = tree[L(rt)].sum + tree[R(rt)].sum;
    tree[rt].sum %= mod;
}
void pushdown(int rt) {
    if(tree[rt].add != 0 || tree[rt].mul != 1){
        tree[L(rt)].sum = tree[L(rt)].sum * tree[rt].mul + tree[rt].add*(tree[L(rt)].r - tree[L(rt)].l + 1);
        tree[L(rt)].sum %= mod;
        tree[L(rt)].mul *= tree[rt].mul;
        tree[L(rt)].mul %= mod;
        tree[L(rt)].add = tree[L(rt)].add * tree[rt].mul + tree[rt].add;
        tree[L(rt)].add %= mod;
        tree[R(rt)].sum = tree[R(rt)].sum * tree[rt].mul + tree[rt].add*(tree[R(rt)].r - tree[R(rt)].l + 1);
        tree[R(rt)].sum %= mod;
        tree[R(rt)].mul *= tree[rt].mul;
        tree[R(rt)].mul %= mod;
        tree[R(rt)].add = tree[R(rt)].add * tree[rt].mul + tree[rt].add;
        tree[R(rt)].add %= mod;
        tree[rt].add = 0;
        tree[rt].mul = 1;
    }
}
void build(int l,int r,int rt) {
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].add = 0;
    tree[rt].mul = 1;
    tree[rt].sum = l;
    if(l == r) {
        return ;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    build(l,mid,L(rt));
    build(mid + 1, r, R(rt));
    tree[rt].sum = tree[L(rt)].sum + tree[R(rt)].sum;
    tree[rt].sum %= mod;
}
void add(int l,int r,ll v,int rt) {
    if(l <= tree[rt].l && r >= tree[rt].r) {
        tree[rt].add += v;
        tree[rt].add %= mod;
        tree[rt].sum += v*(tree[rt].r - tree[rt].l + 1);
        tree[rt].sum %= mod;
        return ;
    }
    pushdown(rt);
    int mid = tree[rt].l + tree[rt].r >> 1;
    if(mid >= r) {
        add(l,r,v,L(rt));
    } else if(l >= mid + 1) {
        add(l,r,v,R(rt));
    } else {
        add(l,mid,v,L(rt));
        add(mid+1,r,v,R(rt));
    }
    pushup(rt);
}
void mul(int l,int r,ll v,int rt) {
    if(l <= tree[rt].l && r >= tree[rt].r) {
        tree[rt].mul *= v;
        tree[rt].mul %= mod;
        tree[rt].add *= v;
        tree[rt].add %= mod;
        tree[rt].sum *= v;
        tree[rt].sum %= mod;
        return ;
    }
    pushdown(rt);
    int mid = tree[rt].l + tree[rt].r >> 1;
    if(mid >= r) {
        mul(l,r,v,L(rt));
    } else if(l >= mid + 1) {
        mul(l,r,v,R(rt));
    } else {
        mul(l,mid,v,L(rt));
        mul(mid + 1, r, v, R(rt));
    }
    pushup(rt);
} 
ll query(int l,int r,int rt) {
    ll sum = 0;
    if(l <= tree[rt].l && r >= tree[rt].r) {
        return tree[rt].sum % mod;
    }
    pushdown(rt);
    int mid = tree[rt].l + tree[rt].r >> 1;
    if(mid >= r) {
        return query(l,r,L(rt)) % mod;
    } else if(l >= mid + 1) {
        return query(l,r,R(rt)) % mod;
    } else {
        sum += query(l,mid,L(rt));
        sum += query(mid+1,r,R(rt));
        return sum % mod;
    }
}
int main() {
	//freopen("input.txt","r",stdin); 
    while(scanf("%d %d",&n,&m) != EOF) {
        build(0,n,1);
        while(m --) {
            scanf("%s",op);
            if(op[0] == 'a') {
                scanf("%d %d %lld",&a,&b,&c);
                add(a,b,c,1);
            } else if(op[0] == 'm') {
                scanf("%d %d %lld",&a,&b,&c);
                mul(a,b,c,1);
            } else {
                scanf("%d %d",&a,&b);
                printf("%lld\n",query(a,b,1));
            }
        }
        puts("");
    }
	return 0;
}