d799 - 区间求和
題目描述
題目要求處理一個包含 N 個數值的陣列，並支援兩種操作：區間加值和區間求和。給定 N 個初始數值，接著有 Q 個操作，每個操作可以是將指定區間 [x, y] 的所有數值加上 k，或是查詢指定區間 [x, y] 的數值總和。
解題思路
本題可以使用二元索引樹 (Binary Indexed Tree, BIT) 來高效地處理區間加值和區間求和操作。BIT 是一種資料結構，可以有效地計算陣列的前綴和，並支援快速更新單個元素。
程式碼中，_BIT 結構體實現了 BIT 的功能。add 函數用於更新 BIT，range_add 函數用於區間加值，ask 函數用於計算前綴和，range_ask 函數用於計算區間和。
為了處理區間加值，我們使用差分陣列的概念。初始時，BIT 儲存的是原始陣列的差分陣列。當我們需要將區間 [x, y] 的所有數值加上 k 時，我們只需要在 BIT 中更新兩個位置：x 加上 k，y+1 減去 k。這樣，當我們計算區間 [l, r] 的和時，BIT 會自動計算差分陣列的前綴和，從而得到區間 [l, r] 的實際和。
複雜度分析
- 時間複雜度: O(Q log N)，其中 Q 是操作的數量，N 是陣列的大小。每個
add、range_add、ask和range_ask操作的時間複雜度都是 O(log N)。 - 空間複雜度: O(N)，BIT 陣列需要 O(N) 的空間。
程式碼
#include <bits/stdc++.h>
#define MAXN 500005
#define ll long long
using namespace std;
ll n,m,ci,ci2,ci3,is;
struct _BIT{
ll N;
ll C[MAXN],C2[MAXN];
ll lowbit(ll x){return x&(-x);}
void init(ll n){
N=n;
memset(C,0,sizeof(C));
memset(C2,0,sizeof(C2));
}
void add(ll pos,ll val){
for(ll i=pos;i<=N;i+=lowbit(i)) C[i]+=val,C2[i]+=val*pos;
}
void range_add(ll l,ll r,ll x){
add(l,x);
add(r+1,-x);
}
ll ask(ll pos){
ll ret=0;
for(ll i=pos;i>0;i-=lowbit(i)) ret+=(pos+1)*C[i]-C2[i];
return ret;
}
ll range_ask(ll l,ll r){
return ask(r)-ask(l-1);
}
}BIT;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n;
BIT.init(n+1);
for(int i=1;i<=n;++i){
cin >> ci;
BIT.add(i,ci);
BIT.add(i+1,-ci);
}
cin >> m;
for(int i=1;i<=m;++i){
cin >> is >> ci >> ci2;
if(is==1){
cin >> ci3;
BIT.range_add(ci,ci2,ci3);
}
else{
cout << BIT.range_ask(ci,ci2) << "\n";
}
}
}