ZeroJudge d799 - 區間求和 解題心得( 題目 )
解題概念:差分BIT
解題方法:這題固然可以使用懶標記+線段樹，但是也可以使用BIT來維護，它的優點是:(1)實作相對線段樹簡單 (2)雖然時間複雜度和線段樹一模一樣，但是常數相對較小。
這題是區間修改，假設區間是L、R，我們固然不能在L到R都做一次單點修改，取而代之的是我們使用區間修改，而BIT的區間修改大概是這樣子的:
維護差分陣列的前綴和di(假設代表差分後的數字)，在更改只需動d(L)和d(R+1)，而我們要維護兩個不同的BIT:
(1)d1,d2,d3,..
(2)d1,2d2,3d3,...
透過(1)、(2)，可快速求得區間值。
Java參考程式碼(有更好意見可留言於下方，謝謝!):
//Author:En Chi Tsung(欉恩祁)
//Date:2022/02/22
import java.util.*;
import java.io.*;
public class zjd799 {
public static final int maxn=500005;
public static long[] bit=new long[maxn];
public static long[] pre=new long[maxn];
public static long[] las=new long[maxn];
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int rd,ret;
public static long q,m;
public static void main(String[] args) throws Exception{
final int n=readint();
for(int i=1;i<=n;i++) {
pre[i]=pre[i-1]+readint();
}
final int q=readint();
int x,l,r,v;
for(int i=0;i<q;i++) {
x=readint();
if(x==1) {
l=readint();
r=readint();
v=readint();
update(l,-v);
update(r+1,v);
}
else{ //x==2
l=readint();
r=readint();
bw.write((query(r)-query(l-1)+pre[r]-pre[l-1])+"\n");
}
}
bw.flush();
}
public static void update(int x,int v) {
for(int i=x;i<maxn;i+=(i&-i)) {
las[i]+=v;
bit[i]+=((long)v*(x-1));
}
}
public static long query(int x) {
q=m=0;
for(int i=x;i>0;i-=(i&-i)) {
q+=bit[i];
}
for(int i=x;i>0;i-=(i&-i)) {
m+=las[i];
}
return q-m*x;
}
public static int readint() throws Exception{
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
}
文章標籤
全站熱搜
