线段树
线段树
线段树
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+6;
const int M = 3e5+7;
#define ll long long
#define en '\n'
#define debug cout<<"------"
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int dx[]= {1,-1,0,0,1,1,-1,-1};
int dy[]= {0,0,1,-1,1,-1,1,-1};
inline ll read() {
char c = getchar();
ll x = 0,s = 1;
while(c < '0' || c > '9') {
if(c == '-') s = -1; //是符号
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x*10 + c -'0'; //是数字
c = getchar();
}
return x*s;
}
inline void write(ll x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x/10);
putchar('0'+x%10);
}
bool isprime(ll x) {
if(x<2||(x%2==0&&x>2))return 0;
for(ll i=3; i<=x/i; i+=2)if(x%i==0)return 0;
return 1;
}
ll qsm(ll x,ll y) {
ll ans=1;
while(y) {
if(y&1)ans=ans*x;
x=x*x;
y>>=1;
}
return ans;
}
struct node {
int l,r;
ll sum,add;
} nd[4*N];
void build(int id,int l,int r) {
nd[id].l=l;
nd[id].r=r;
if(l==r) {
cin>>nd[id].sum;
return ;
}
int mid = l+r>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
nd[id].sum=nd[id*2].sum+nd[id*2+1].sum;
}
void pushdown(int id) {
if(nd[id].add) {
nd[id*2].sum+=(nd[id*2].r-nd[id*2].l+1)*nd[id].add;
nd[id*2+1].sum+=(nd[id*2+1].r-nd[id*2+1].l+1)*nd[id].add;
nd[id*2].add+=nd[id].add;
nd[id*2+1].add+=nd[id].add;
nd[id].add=0;
}
}
void pushup(int id) {
nd[id].sum=nd[id*2].sum+nd[id*2+1].sum;
}
void updata(int id,int l,int r,ll k) {
if(nd[id].l>=l&&nd[id].r<=r) {
nd[id].sum+=(nd[id].r-nd[id].l+1)*k;
nd[id].add+=k;
return ;
}
int mid = nd[id].l+nd[id].r>>1;
pushdown(id);
if(l<=mid)updata(id*2,l,r,k);
if(r>=mid+1)updata(id*2+1,l,r,k);
pushup(id);
}
ll query(int id,int l,int r) {
// cout<<nd[id].l<<" "<<nd[id].r<<en;
if(nd[id].l>=l&&nd[id].r<=r)return nd[id].sum;
int mid = nd[id].l+nd[id].r>>1;
ll sum=0;
pushdown(id);
if(l<=mid)sum+=query(id*2,l,r);
if(r>=mid+1)sum+=query(id*2+1,l,r);
return sum;
}
void solve() {
int n,q;
cin>>n>>q;
build(1,1,n);
int l,r;
ll k;
while(q--) {
int op;
cin>>op;
if(op==1) {
cin>>l>>r>>k;
updata(1,l,r,k);
} else {
cin>>l>>r;
ll sum=query(1,l,r);
cout<<sum<<en;
}
}
}
int main() {
//fast
int t;
t=1;
cin>>t;
while(t--) {
solve();
cout<<en;
}
}
本文由作者按照 CC BY 4.0 进行授权