线段树-两种操作
线段树是一种二叉树结构，能够在lg(n)的复杂度下完成一些计算。
最长见的就是数列求和之类的，而且还能够支持单点修改甚至是区间修改。
线段树的精髓在于懒惰标记，也就是说，在更新的时候，不更新全部子节点，只会打一个标记。
比如说一段区间要加一个值，它不会在每个叶子节点加上相应数值，而是在覆盖需要修改的子节点的区间上加一个tag要加多少，相应的因为要保证上层计算无误，所以要根据自己的孩子数更新自己的sum值。
如果下次要更新这段覆盖的区间的子区间，可以把相应的标记下放。
线段树支持两种操作其实也比较简单，就是考虑两种操作的优先级，根据优先级判断相关节点应该怎么操作。
下面是一个乘和加两种操作的例子。
/*
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;
}