树状数组

一种简单的数据结构。可以做到 O(log⁡n)O(\log n) 单点修改，O(log⁡n)O(\log n) 区间查询。
维护差分数组可做到 O(log⁡n)O(\log n) 区间修改，O(log⁡n)O(\log n) 单点查询。

每个元素管理的区间为[i-lowbit(i)+1,i]，lowbit为二进制数的最低位1以及之后的0所组成的数。

1
2
3
int lowbit(int x){
    return x&(-x);
}

在补码规则下，x的相反数的二进制表示为~x+1，对x取反后+1，把末尾的0（取反为了1）全部进位到了最低位1的位置，进行位与后得到的便是最低位。

洛谷P3374 【模板】树状数组 1

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 5e5+5;
int n;  
int a[N];
int lowbit(int x){
    return x&(-x);
}
ll query(int x){
    ll ans = 0;
    while(x){
        ans += a[x];
        x -= lowbit(x);
    }
    return ans;
}
void modify(int x,int k){
    while(x<=n){
        a[x]+=k;
        x+=lowbit(x);
    }
}


int main(){
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        modify(i,x);
    }
    while(m--){
        int p,q,o;
        scanf("%d%d%d",&p,&q,&o);
        if(p==1)modify(q,o);
        else printf("%lld\n",query(o)-query(q-1));
    }
    return 0;
}

洛谷P3374 【模板】树状数组 2

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 5e5+5;
int n;  
int a[N];
int lowbit(int x){
    return x&(-x);
}
ll query(int x){
    ll ans = 0;
    while(x){
        ans += a[x];
        x -= lowbit(x);
    }
    return ans;
}
void modify(int x,int k){
    while(x<=n){
        a[x]+=k;
        x+=lowbit(x);
    }
}


int main(){
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        modify(i,x);
        modify(i+1,-x);
    }
    while(m--){
        int p;scanf("%d",&p);
        if(p==1){
            int x,y,k;
            scanf("%d%d%d",&x,&y,&k);
            modify(x,k);
            modify(y+1,-k);
        }
        else{
            int x;scanf("%d",&x);
            printf("%lld\n",query(x));
        }
    }
    return 0;
}

区间修改+区间查询

如果同时维护两个树状数组，可以做到 O(log⁡n)O(\log n) 区间修改，O(log⁡n)O(\log n) 区间查询。

考虑差分数组d

a1+a2+⋯+an=d1+(d1+d2)+⋯+(d1+d2+⋯+dn)=n×d1+(n−1)×d2+⋯+(n−(n−1))×dn=n∑i=1ndi−∑i=1n(i−1)di\begin{aligned} &a_1+a_2+\dots +a_n\\ &= d_1 + (d_1+d_2)+\dots + (d_1+d_2+\dots + d_n) \\ &= n\times d_1 + (n-1)\times d_2 + \dots + (n-(n-1))\times d_n \\ &= n \sum_{i=1}^n d_i - \sum_{i=1}^n (i-1) d_i \end{aligned}

则我们同时维护d和(i-1)*d即可

洛谷P3372 【模板】线段树 1

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e5+5;
int n;  
ll a1[N],a2[N];
int lowbit(int x){
    return x&(-x);
}
ll query1(int x){
    ll ans = 0;
    while(x){
        ans += a1[x];
        x -= lowbit(x);
    }
    return ans;
}
ll query2(int x){
    ll ans = 0;
    while(x){
        ans += a2[x];
        x-=lowbit(x);
    }
    return ans;
}
ll query(int x){
    return (ll)x * query1(x) - query2(x);
}
void modify1(int x,ll k){
    while(x<=n){
        a1[x]+=k;
        x+=lowbit(x);
    }
}
void modify2(int x,ll k){
    while(x<=n){
        a2[x]+=k;
        x+=lowbit(x);
    }
}
void modify(int l,int r,ll k){
    modify1(l,k);
    modify2(l,(l-1)*k);
    modify1(r+1,-k);
    modify2(r+1,-r*k);
}


int main(){
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        ll x;scanf("%lld",&x);
        modify(i,i,x);
    }
    while(m--){
        int p;scanf("%d",&p);
        if(p==1){
            ll x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            modify(x,y,k);
        }
        else{
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(y)-query(x-1));
        }
    }
    return 0;
}

事实证明，树状数组比线段树常数略小 (200ms vs 300ms)，但是树状数组支持的操作有限。

二维区间修改+区间查询

洛谷P4514 上帝造题的七分钟

定义二维差分 di,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1d_{i,j} = a_{i,j} - a_{i-1,j} - a_{i,j-1} + a_{i-1,j-1}，此时有 ax,y=∑i=1x∑j=1ydi,ja_{x,y}=\sum_{i=1}^x\sum_{j=1}^y d_{i,j}。

用线段树进行区间修改，在modify()中，每次第i行减少lowbit(i)，第j列减少lowbit(j)，时间复杂度 O(log⁡nlog⁡m)O(\log n \log m)

如何进行区间查询？仿照一维情况推导公式：

∑i=1n∑j=1mai,j=∑i=1n∑j=1m∑k=1i∑l=1jdk,l=∑i=1n∑j=1m(n−i+1)(m−j+1)di,j=∑i=1n∑j=1m[nm−m(i−1)−n(j−1)+(i−1,j−1)]di,j=nm∑i=1n∑j=1mdi,j−m∑i=1n∑j=1m(i−1)di,j−n∑i=1n∑j=1m(j−1)di,j+∑i=1n∑j=1m(i−1)(j−1)di,j\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m a_{i,j}\\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^i\sum_{l=1}^j d_{k,l}\\ &=\sum_{i=1}^n\sum_{j=1}^m (n-i+1)(m-j+1)d_{i,j}\\ &=\sum_{i=1}^n\sum_{j=1}^m [nm-m(i-1)-n(j-1)+(i-1,j-1)]d_{i,j} \\ &=nm\sum_{i=1}^n\sum_{j=1}^m d_{i,j} - m\sum_{i=1}^n\sum_{j=1}^m (i-1)d_{i,j} - n\sum_{i=1}^n\sum_{j=1}^m (j-1)d_{i,j} + \sum_{i=1}^n\sum_{j=1}^m (i-1)(j-1)d_{i,j} \end{aligned}

维护4个二维树状数组即可。

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
#include<bits/stdc++.h>
using namespace std;

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

const int N = 2052;
int n,m;
int t1[N][N],t2[N][N],t3[N][N],t4[N][N];

void modify(int x,int y,int k){
    for(int i=x;i<=n;i+=lowbit(i)){
        for(int j=y;j<=m;j+=lowbit(j)){
            t1[i][j] += k;
            t2[i][j] += k * (x-1);
            t3[i][j] += k * (y-1);
            t4[i][j] += k * (x-1)*(y-1);
        }
    }
}

int query(int x,int y){
    int ans = 0;
    for(int i=x;i;i-=lowbit(i)){
        for(int j=y;j;j-=lowbit(j)){
            ans += x*y*t1[i][j] - y*t2[i][j] - x *t3[i][j] + t4[i][j];
        }
    }
    return ans;
}

char o[2];

int main(){
    scanf("X %d %d",&n,&m);
    int a,b,c,d,k;
    while(scanf("%s",o)==1){
        if(o[0]=='L'){
            scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
            modify(a,b,k);
            modify(a,d+1,-k);
            modify(c+1,b,-k);
            modify(c+1,d+1,k);
        }
        else{
            scanf("%d%d%d%d",&a,&b,&c,&d);
            printf("%d\n",query(c,d)-query(c,b-1)-query(a-1,d)+query(a-1,b-1));
        }
    }
    return 0;
}

线段树

一种常见用来维护区间信息的数据结构

线段树可以在 O(log⁡N)O(\log N) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树维护的信息在很多时候可以认为是满足（幺）半群的性质的信息。

线段树原理可参照OI Wiki，本文略去。

二叉树实现

洛谷P3372 【模板】线段树 1
用二叉树实现，数组一定要开4*N大小！

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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll d[N*4]; //四倍空间
ll tag[N*4];

ll tmp[N];

#include<bits/stdc++.h>
using namespace std;

/*
0.开long long
1.注意极限情况
2.多测要清零！！！！
3.注意输入方式 有没有测试数据组数
4.注意各种越界
5.检查数据范围 数组有没有开小
6.不用指针，会RE 自己写数组模拟
*/

#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define begend(x) x.begin(),x.end()

#define mem0(x) memset(x,0,sizeof(x))
#define meminf(x) memset(x,0x3f,sizeof(x));

#define YES puts("YES")
#define NO puts("NO")
#define FLAG(x) if(x)YES;else NO;


int read(){
    int f=1,x=0;
    char c;
    c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

template <class T>
T read(){
    T f=1,x=0;
    char c;
    c=getchar();
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}


template <class T>
inline void print(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}

#define left (o<<1)
#define right (o<<1|1)

const int N = 1e5+5;

ll d[N*4]; //四倍空间
ll tag[N*4];

ll tmp[N];


void build(int l,int r,int o){
    if(l==r){
        d[o] = tmp[l];
        // printf("build %d %d = %lld\n",l,r,d[o]);
        return;
    }
    int mid = l +((r-l)>>1);
    build(l,mid,left);
    build(mid+1,r,right);
    d[o] = d[left] + d[right];
    // printf("build %d %d = %lld\n",l,r,d[o]);
}
void pushdown(int l,int r,int o){
    if(tag[o] && l!=r){
        int mid = l + ((r-l)>>1);
        d[left] += tag[o] * (mid-l+1);
        d[right] += tag[o] * (r-mid);
        tag[left] += tag[o];
        tag[right] += tag[o];
        tag[o]=0;
    }
}
// 统一规定：[x,y]是查询的区间
ll query(int l,int r,int o,int x,int y){
    if(x<=l && r<=y){
        // printf("(%d %d) = %lld\n",l,r,d[o]);
        return d[o];
    }
    pushdown(l,r,o);

    int mid = l + ((r-l)>>1); //mid一定这么写
    ll rt = 0;
    if(x<=mid){
        rt += query(l,mid,left,x,y);
    }
    if(y>mid){
        rt += query(mid+1,r,right,x,y);
    }
    // printf("(%d %d) = %lld\n",l,r,rt);
    return rt;
}
void modify(int l,int r,int o,int x,int y,int k){
    if(x<=l && r<=y){
        d[o] += (r-l+1)*k;
        tag[o] += k;
        return;
    }
    pushdown(l,r,o);
    int mid = l + ((r-l)>>1); //mid一定这么写
    if(x<=mid){
        modify(l,mid,left,x,y,k);
    }
    if(y>mid){
        modify(mid+1,r,right,x,y,k);
    }
    d[o] = d[left]+d[right];
}


int main(){
    int n=read(),m=read();
    for(int i=1;i<=n;i++){
        tmp[i]=read();
        // printf("read %d %lld\n",i,tmp[i]);
    }
    build(1,n,1);
    for(int i=0;i<m;i++){
        int k=read();
        if(k==1){
            int a=read(),b=read(),c=read();
            modify(1,n,1,a,b,c);
        }
        else{
            int a=read(),b=read();
            print(query(1,n,1,a,b));
            putchar('\n');
        }
    }
    return 0;
}

void build(int l,int r,int o){
    if(l==r){
        d[o] = tmp[l];
        return;
    }
    int mid = l +((r-l)>>1);
    build(l,mid,left);
    build(mid+1,r,right);
    d[o] = d[left] + d[right];
}
void pushdown(int l,int r,int o){
    if(tag[o] && l!=r){
        int mid = l + ((r-l)>>1);
        d[left] += tag[o] * (mid-l+1);
        d[right] += tag[o] * (r-mid);
        tag[left] += tag[o];
        tag[right] += tag[o];
        tag[o]=0;
    }
}
ll query(int l,int r,int o,int x,int y){
    if(x<=l && r<=y){
        return d[o];
    }
    pushdown(l,r,o);

    int mid = l + ((r-l)>>1);
    ll rt = 0;
    if(x<=mid){
        rt += query(l,mid,left,x,y);
    }
    if(y>mid){
        rt += query(mid+1,r,right,x,y);
    }
    return rt;
}
void modify(int l,int r,int o,int x,int y,int k){
    if(x<=l && r<=y){
        d[o] += (r-l+1)*k;
        tag[o] += k;
        return;
    }
    pushdown(l,r,o);
    int mid = l + ((r-l)>>1);
    if(x<=mid){
        modify(l,mid,left,x,y,k);
    }
    if(y>mid){
        modify(mid+1,r,right,x,y,k);
    }
    d[o] = d[left]+d[right];
}


int main(){
    int n=read(),m=read();
    for(int i=1;i<=n;i++){
        tmp[i]=read();
    }
    build(1,n,1);
    for(int i=0;i<m;i++){
        int k=read();
        if(k==1){
            int a=read(),b=read(),c=read();
            modify(1,n,1,a,b,c);
        }
        else{
            int a=read(),b=read();
            print(query(1,n,1,a,b));
            putchar('\n');
        }
    }
    return 0;
}

例1

HDU-4027 Can you answer these queries?

维护一个数据结构，支持区间开方（向下取整），区间求和。保证所有数小于2632^{63}。

我们可以发现，一个数最多开7次方就会变成1，所以在update时，如果遇到区间和等于r-l+1，说明区间内都是1，可以直接返回。

直接暴力区间修改即可。

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
#include<bits/stdc++.h>
using namespace std;

#define ll long long


const int N = 1e5+5;

int n;
ll t[N*4];
ll a[N];

void build(int o,int l,int r){
    if(l==r){
        t[o]=a[l];
        return;
    }
    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;
    build(lch,l,mid);build(rch,mid+1,r);
    t[o]=t[lch]+t[rch];
}

int ql,qr;
void update(int o,int l,int r){
    if(t[o]==(r-l+1))return;
    if(l==r){
        t[o] = (ll)sqrt(t[o]);
        return;
    }
    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;
    if(ql<=mid) update(lch,l,mid);
    if(qr>mid) update(rch,mid+1,r);
    t[o]=t[lch]+t[rch];
}

ll query(int o,int l,int r){
    if(ql<= l && r<=qr){
        return t[o];
    }
    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;
    
    ll ans = 0;
    if(ql<=mid) ans += query(lch,l,mid);
    if(qr>mid) ans += query(rch,mid+1,r);
    return ans;
}

void solve(){
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    build(1,1,n);
    int m;scanf("%d",&m);
    while(m--){
        int o;
        scanf("%d%d%d",&o,&ql,&qr);
        if(ql>qr)swap(ql,qr);

        if(o==0)update(1,1,n);
        else printf("%lld\n",query(1,1,n));
    }
}

int main(){
    int T=0;
    while(scanf("%d",&n)==1){
        T++;
        printf("Case #%d:\n",T);
        solve();
        puts("");
    }
    return 0;
}

例2

HDU-4578 Transformation

维护一个数据结构，支持区间加，区间乘，区间修改，区间求和，区间求平方和，区间求立方和。

考虑3个lazy tag add，mul，change，每个节点维护3个信息sum1，sum2，sum3 ，分别维护和、平方和、立方和。

对三种操作和pushdown分别推导公式：

设区间为 [l,r][l,r]，操作数为 dd。

  1. 区间加操作

    sum1′=sum1+(r−l+1)dsum2′=(al+d)2+⋯+(ar+d)2=(al2+⋯+ar2)+2d(al+⋯+ar)+(r−l+1)d2=sum2+2dsum1+(r−l+1)d2sum3′=(al+d)3+⋯+(ar+d)3=(al3+⋯+ar3)+3d2(al+⋯+ar)+3d(al2+⋯+ar2)+(r−l+1)d3=sum3+3dsum2+3d2sum1+(r−l+1)d2 \begin{aligned}\text{sum1}'&=\text{sum1}+(r-l+1)d\\ \text{sum2}'&=(a_l+d)^2+\dots+(a_r+d)^2\\ &=(a_l^2+\dots+a_r^2)+2d(a_l+\dots+a_r)+(r-l+1)d^2\\ &=\text{sum2}+2d\text{sum1}+(r-l+1)d^2\\ \text{sum3}'&=(a_l+d)^3+\dots+(a_r+d)^3\\ &=(a_l^3+\dots+a_r^3)+3d^2(a_l+\dots+a_r)+3d(a_l^2+\dots+a_r^2)+(r-l+1)d^3\\ &=\text{sum3}+3d\text{sum2}+3d^2\text{sum1}+(r-l+1)d^2\\ \end{aligned}

    在修改区间加操作时，要按 sum3\text{sum3}，sum2\text{sum2}，sum1\text{sum1}的顺序进行操作，以免覆盖。

    同时add标记加上d。

  2. 区间乘操作

    sum1′=sum1×dsum2′=sum1×d2sum3′=sum1×d3\begin{aligned} \text{sum1}'&=\text{sum1}\times d\\ \text{sum2}'&=\text{sum1}\times d^2\\ \text{sum3}'&=\text{sum1}\times d^3\\ \end{aligned}

    并且add标记、mul标记都乘上d。

  3. 区间修改操作

    sum1′=(r−l+1)×dsum2′=(r−l+1)×d2sum3′=(r−l+1)×d3\begin{aligned} \text{sum1}'&=(r-l+1)\times d\\ \text{sum2}'&=(r-l+1)\times d^2\\ \text{sum3}'&=(r-l+1)\times d^3\\ \end{aligned}

    此时，修改change标记为d，并初始化mul标记为1，add标记为0。

  4. pushdown操作

    若该节点有change标记，则进行如下操作。

    • 修改左右儿子的change标记
    • 左右儿子的mul标记、add标记初始化
    • 修改左右儿子的sum3\text{sum3}，sum2\text{sum2}，sum1\text{sum1}

    然后，处理add标记和mul标记

    对于左儿子和右儿子，处理方法相同。

    设左儿子或右儿子的区间为 [l,r][l,r]，设mul标记为 mm，add标记为 aa。

    sum1′=(mal+a)+⋯+(mar+a)=msum1+(r−l+1)asum2′=(mal+a)2+⋯+(mar+a)2=m2(al2+⋯+ar2)+2ma(al+⋯+ar)+(r−l+1)a2=m2sum2+2masum1+(r−l+1)d2sum3′=(mal+a)3+⋯+(mar+a)3=m3(al3+⋯+ar3)+3ma2(al+⋯+ar)+3m2a(al2+⋯+ar2)+(r−l+1)a3=sum3+3m2asum2+3ma2sum1+(r−l+1)a2\begin{aligned} \text{sum1}'&=(ma_l+a)+\dots+(ma_r+a)\\ &=m\text{sum1}+(r-l+1)a\\ \text{sum2}'&=(ma_l+a)^2+\dots+(ma_r+a)^2\\ &=m^2(a_l^2+\dots+a_r^2)+2ma(a_l+\dots+a_r)+(r-l+1)a^2\\ &=m^2\text{sum2}+2ma\text{sum1}+(r-l+1)d^2\\ \text{sum3}'&=(ma_l+a)^3+\dots+(ma_r+a)^3\\ &=m^3(a_l^3+\dots+a_r^3)+3ma^2(a_l+\dots+a_r)\\ &\quad+3m^2a(a_l^2+\dots+a_r^2)+(r-l+1)a^3\\ &=\text{sum3}+3m^2a\text{sum2}+3ma^2\text{sum1}+(r-l+1)a^2\\ \end{aligned}

    这里也要按 sum3\text{sum3}，sum2\text{sum2}，sum1\text{sum1}的顺序进行操作，以免覆盖。

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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MOD = 10007;

int squared(int x){
    return (x*x)%MOD;
}
int cubed(int x){
    return (squared(x)%MOD*x%MOD)%MOD;
}

const int N = 1e5+5;

int sum1[N*4],sum2[N*4],sum3[N*4];
int add[N*4],mul[N*4],change[N*4];

int ql,qr,qk;
void init(int o,int l,int r){
    mul[o]=1;
    sum1[o]=0;sum2[o]=0,sum3[o]=0;
    add[o]=0,change[o]=0;
    if(l==r)return;
    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;
    init(lch,l,mid);
    init(rch,mid+1,r);
}
void pushup(int o,int l,int r){
    int lch = o<<1, rch = (o<<1) +1;
    sum1[o] = sum1[lch]+sum1[rch]; sum1[o]%=MOD;
    sum2[o] = sum2[lch]+sum2[rch]; sum2[o]%=MOD;
    sum3[o] = sum3[lch]+sum3[rch]; sum3[o]%=MOD;
}
void pushdown(int o,int l,int r){
    if(l==r)return;

    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;
    // 有change
    if(change[o]){
        change[lch]=change[rch]=change[o];
        
        sum1[lch] = (mid-l+1)*change[o],sum1[lch]%=MOD;
        sum1[rch] = (r-mid)*change[o],sum1[rch]%=MOD;
        
        sum2[lch] = (mid-l+1)*squared(change[o]);sum2[lch]%=MOD;
        sum2[rch] = (r-mid)*squared(change[o]),sum2[rch]%=MOD;
 
        sum3[lch] = (mid-l+1)*cubed(change[o]),sum3[lch]%=MOD;
        sum3[rch] = (r-mid)*cubed(change[o]),sum3[rch]%=MOD;

        mul[lch]=mul[rch]=1;
        add[lch]=add[rch]=0;
    }
    // a+2 *5
    // a* 5 + 10

    // 先乘再加
    mul[lch] *= mul[o], mul[lch]%=MOD;
    mul[rch] *= mul[o], mul[rch]%=MOD;
    add[lch] *= mul[o], add[lch]%=MOD;
    add[rch] *= mul[o], add[rch]%=MOD;
    add[lch] += add[o], add[lch]%=MOD;
    add[rch] += add[o], add[rch]%=MOD;

    sum3[lch] *= cubed(mul[o]), sum3[lch]%=MOD;
    sum3[lch] += (3*add[o]*sum2[lch]%MOD*mul[o]*mul[o])%MOD + 
                (3*squared(add[o])%MOD*sum1[lch]*mul[o])%MOD + 
                (mid-l+1)*cubed(add[o]) %MOD;
    sum3[lch] %= MOD;
    sum3[rch] *= cubed(mul[o]), sum3[rch]%=MOD;
    sum3[rch] += (3*add[o]*sum2[rch]%MOD*mul[o]*mul[o])%MOD + 
                (3*squared(add[o])%MOD*sum1[rch]*mul[o])%MOD + 
                (r-mid)*cubed(add[o]) %MOD;
    sum3[rch] %= MOD;

    
    sum2[lch] *= squared(mul[o]), sum2[lch]%=MOD;
    sum2[lch] += (2*add[o]*sum1[lch]*mul[o] +
        (mid-l+1)*squared(add[o]))%MOD;
    sum2[lch]%=MOD;
    sum2[rch] *= squared(mul[o]), sum2[rch]%=MOD;
    sum2[rch] += (2*add[o]*sum1[rch]*mul[o] + 
        (r-mid)*squared(add[o]))%MOD;
    sum2[rch]%=MOD;

    sum1[lch] *= mul[o], sum1[lch]%=MOD;
    sum1[lch] += (mid-l+1)*add[o], sum1[lch]%=MOD;
    sum1[rch] *= mul[o], sum1[rch]%=MOD;
    sum1[rch] += (r-mid)*add[o], sum1[rch]%=MOD;


    change[o]=0,mul[o]=1,add[o]=0;
}

int query1(int o,int l,int r){
    if(ql<=l&&r<=qr)return sum1[o];
    pushdown(o,l,r);
    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;
    int ans = 0;
    if(ql<=mid) ans+=query1(lch,l,mid),ans%=MOD;
    if(qr>mid) ans+=query1(rch,mid+1,r),ans%=MOD;
    return ans;
}
int query2(int o,int l,int r){
    if(ql<=l&&r<=qr)return sum2[o];
    pushdown(o,l,r);
    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;
    int ans = 0;
    if(ql<=mid) ans+=query2(lch,l,mid),ans%=MOD;
    if(qr>mid) ans+=query2(rch,mid+1,r),ans%=MOD;
    return ans;
}
int query3(int o,int l,int r){
    if(ql<=l&&r<=qr)return sum3[o];
    pushdown(o,l,r);
    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;
    int ans = 0;
    if(ql<=mid) ans+=query3(lch,l,mid),ans%=MOD;
    if(qr>mid) ans+=query3(rch,mid+1,r),ans%=MOD;
    return ans;
}

void modify_add(int o,int l,int r){
    if(ql<=l&&r<=qr){
        sum3[o] += (r-l+1)*cubed(qk)%MOD + 3*qk*sum2[o]%MOD + 3*qk*qk*sum1[o]%MOD; 
        sum3[o] %= MOD;
        sum2[o] += (r-l+1)*squared(qk) + 2*qk*sum1[o]; sum2[o]%=MOD;
        sum1[o] += (r-l+1)*qk; sum1[o]%=MOD;
        add[o] += qk; add[o]%=MOD;
        // if(change[o])change[o] += qk,change[o]%=MOD;
        return;
    }
    pushdown(o,l,r);
    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;

    if(ql<=mid) modify_add(lch,l,mid);
    if(qr>mid) modify_add(rch,mid+1,r);
    pushup(o,l,r);
}
void modify_mul(int o,int l,int r){
    if(ql<=l&&r<=qr){
        sum1[o] *= qk; sum1[o]%=MOD;
        sum2[o] *= squared(qk); sum2[o]%=MOD;
        sum3[o] *= cubed(qk); sum3[o] %= MOD;
        mul[o] *= qk; mul[o]%=MOD;
        add[o] *= qk; add[o]%=MOD;
        // if(change[o])change[o] *= qk,change[o]%=MOD;
        return;
    }
    pushdown(o,l,r);
    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;

    if(ql<=mid) modify_mul(lch,l,mid);
    if(qr>mid) modify_mul(rch,mid+1,r);

    pushup(o,l,r);
}
void modify_change(int o,int l,int r){
    if(ql<=l&&r<=qr){
        sum1[o] = qk*(r-l+1); sum1[o]%=MOD;
        sum2[o] = squared(qk)*(r-l+1); sum2[o]%=MOD;
        sum3[o] = cubed(qk)*(r-l+1); sum3[o]%=MOD;
        change[o] = qk; change[o]%=MOD;
        mul[o]=1;add[o]=0;
        return;
    }
    // 1e18 1e4*1e4*1e4
    pushdown(o,l,r);
    int mid = (l+r)>>1;
    int lch = o<<1, rch = (o<<1) +1;

    if(ql<=mid) modify_change(lch,l,mid);
    if(qr>mid) modify_change(rch,mid+1,r);

    pushup(o,l,r);
}

// 1~2 sum3 = 15
// 

int n,m;
bool solve(){
    scanf("%lld%lld",&n,&m);
    if(n==0)return 0;
    init(1,1,n); 
    while(m--){
        int a;
        scanf("%lld%lld%lld%lld",&a,&ql,&qr,&qk);
        if(a==1)modify_add(1,1,n);
        else if(a==2)modify_mul(1,1,n);
        else if(a==3)modify_change(1,1,n);
        else{
            if(qk==1)printf("%lld\n",query1(1,1,n)%MOD);
            if(qk==2)printf("%lld\n",query2(1,1,n)%MOD);
            if(qk==3)printf("%lld\n",query3(1,1,n)%MOD);
        }

    }
    return 1;
}

signed main(){
    while(solve());
    return 0;
}