icontofig | 发布于 2019-08-29 22:08:21 | 阅读量 488 | 线段树

## 题目大意

1.询问l---r之间所有数按题目中格式公式的计算求和。

2.更改序列某个位置的值。

## 代码

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
struct tree{
ll sum1,sum2;
int l,r;
}tr[maxn<<2];
ll a[maxn];
int n,q;
void push_up(int now){
tr[now].sum1 = tr[now<<1].sum1 + tr[now<<1|1].sum1;
tr[now].sum2 = tr[now<<1].sum2 + tr[now<<1|1].sum2;
return;
}
void build(int now,int l,int r){
tr[now].l = l;
tr[now].r = r;
tr[now].sum1 = tr[now].sum2 = 0;
if(l == r){
tr[now].sum1 = a[l];
tr[now].sum2 = a[l] * (n - l + 1);
return;
}
int mid = (l + r) >> 1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
push_up(now);
return;
}
void update(int now,int pos){
if(tr[now].l == tr[now].r){
tr[now].sum1 = a[pos];
tr[now].sum2 = a[pos] * (n - pos + 1);
return;
}
int mid = (tr[now].l + tr[now].r) >> 1;
if(pos <= mid)update(now<<1,pos);
else update(now<<1|1,pos);
push_up(now);
return;
}
ll query1(int now,int l,int r){
if(tr[now].l >= l && tr[now].r <= r){
return tr[now].sum1;
}
ll ret = 0;
int mid = (tr[now].l + tr[now].r) >> 1;
if(l <= mid) ret += query1(now<<1,l,r);
if(r > mid)ret += query1(now<<1|1,l,r);
return ret;
}
ll query2(int now,int l,int r){
if(tr[now].l >= l && tr[now].r <= r){
return tr[now].sum2;
}
ll ret = 0;
int mid = (tr[now].l + tr[now].r) >> 1;
if(l <= mid)ret += query2(now<<1,l,r);
if(r > mid)ret += query2(now<<1|1,l,r);
return ret;
}
int opt,l,r;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 1;i <= n;++i){
cin >> a[i];
}
build(1,1,n);
ll ans;
while(q--){
cin >> opt >> l >> r;
if(opt == 1){
ans = query2(1,l,r) - query1(1,l,r) * (n - r);
cout << ans << "\n";
}
else{
a[l] = r;
update(1,l);
}
}
return 0;
}```

488 人读过

0 条评论