# ZeroJudge d799. 區間求和
[d799. 區間求和 (題目連結)](https://zerojudge.tw/ShowProblem?problemid=d799)
###### * 記得使用 long long
**線段樹做法**
<font color="#00CE17">**AC**</font> **(0.7s, 16.9MB)**
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n, st[N << 2], tag[N << 2];
//建立segment tree
void build(int pos, int x, int v = 1, int l = 0, int r = n - 1){
if(l == r){
st[v] = x; return;
}
int m = (l + r) >> 1;
if(pos <= m) build(pos, x, v << 1, l, m);
else build(pos, x, v << 1 | 1, m + 1, r);
st[v] = st[v << 1] + st[v << 1 | 1];
}
//將tag的值加入st,並將tag標記下推
void push(int v, int l, int r){
st[v] += tag[v] * (r - l + 1);
if(l != r){
tag[v << 1] += tag[v];
tag[v << 1 | 1] += tag[v];
}
tag[v] = 0;
}
//資料更新,向下設立tag
void upd(int ql, int qr, int x, int v = 1, int l = 0, int r = n - 1){
if(tag[v]) push(v, l, r);
st[v] += x * (qr - ql + 1);
if(ql == l && qr == r){
if(l != r){
tag[v << 1] += x;
tag[v << 1 | 1] += x;
}
return;
}
int m = (l + r) >> 1;
if(qr <= m) upd(ql, qr, x, v << 1, l, m);
else if(ql > m) upd(ql, qr, x, v << 1 | 1, m + 1, r);
else{
upd(ql, m, x, v << 1, l, m);
upd(m + 1, qr, x, v << 1 | 1, m + 1, r);
}
}
//區間查詢
int qry(int ql, int qr, int v = 1, int l = 0, int r = n - 1){
if(tag[v]) push(v, l, r);
if(ql == l && qr == r) return st[v];
int m = (l + r) >> 1;
if(qr <= m) return qry(ql, qr, v << 1, l, m);
else if(ql > m) return qry(ql, qr, v << 1 | 1, m + 1, r);
else return qry(ql, m, v << 1, l, m) + qry(m + 1, qr, v << 1 | 1, m + 1, r);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0; i<n; i++){
int x;
cin>>x;
build(i, x);
}
int q;
cin>>q;
while(q--){
int v;
cin>>v;
if(v == 1){
int x, y, k;
cin>>x>>y>>k;
x--, y--;
upd(x, y, k);
}
else{
int x, y;
cin>>x>>y;
x--, y--;
cout<<qry(x, y)<<'\n';
}
}
return 0;
}
```
###### 闕以諾 2022/7/6
###### tags: `C++` `ZeroJudge`