線段樹(shù)是一種二叉樹(shù)結(jié)構(gòu)，能夠在O(logn)時(shí)間復(fù)雜度之內(nèi)實(shí)現(xiàn)對(duì)數(shù)組中某一區(qū)間的增刪改查的操作。
關(guān)于線段樹(shù)的
詳細(xì)解釋。
今天我們涉及的是線段樹(shù)的單點(diǎn)更新以及區(qū)間查詢(xún)功能。
我們以HDU上面的
敵兵布陣為例。
題目描述：
C國(guó)的死對(duì)頭A國(guó)這段時(shí)間正在進(jìn)行軍事演習(xí)，所以C國(guó)間諜頭子Derek和他手下Tidy又開(kāi)始忙乎了。A國(guó)在海岸線沿直線布置了N個(gè)工兵營(yíng)地,Derek和Tidy的任務(wù)就是要監(jiān)視這些工兵營(yíng)地的活動(dòng)情況。由于采取了某種先進(jìn)的監(jiān)測(cè)手段，所以每個(gè)工兵營(yíng)地的人數(shù)C國(guó)都掌握的一清二楚,每個(gè)工兵營(yíng)地的人數(shù)都有可能發(fā)生變動(dòng)，可能增加或減少若干人手,但這些都逃不過(guò)C國(guó)的監(jiān)視。
中央情報(bào)局要研究敵人究竟演習(xí)什么戰(zhàn)術(shù),所以Tidy要隨時(shí)向Derek匯報(bào)某一段連續(xù)的工兵營(yíng)地一共有多少人,例如Derek問(wèn):“Tidy,馬上匯報(bào)第3個(gè)營(yíng)地到第10個(gè)營(yíng)地共有多少人!”Tidy就要馬上開(kāi)始計(jì)算這一段的總?cè)藬?shù)并匯報(bào)。但敵兵營(yíng)地的人數(shù)經(jīng)常變動(dòng)，而Derek每次詢(xún)問(wèn)的段都不一樣，所以Tidy不得不每次都一個(gè)一個(gè)營(yíng)地的去數(shù)，很快就精疲力盡了，Derek對(duì)Tidy的計(jì)算速度越來(lái)越不滿(mǎn):"你個(gè)死肥仔，算得這么慢，我炒你魷魚(yú)!”Tidy想：“你自己來(lái)算算看，這可真是一項(xiàng)累人的工作!我恨不得你炒我魷魚(yú)呢!”無(wú)奈之下，Tidy只好打電話向計(jì)算機(jī)專(zhuān)家Windbreaker求救,Windbreaker說(shuō)：“死肥仔，叫你平時(shí)做多點(diǎn)acm題和看多點(diǎn)算法書(shū)，現(xiàn)在嘗到苦果了吧!”Tidy說(shuō)："我知錯(cuò)了。。。"但Windbreaker已經(jīng)掛掉電話了。Tidy很苦惱，這么算他真的會(huì)崩潰的，聰明的讀者，你能寫(xiě)個(gè)程序幫他完成這項(xiàng)工作嗎？不過(guò)如果你的程序效率不夠高的話，Tidy還是會(huì)受到Derek的責(zé)罵的.
Java代碼：
import java.io.*;
public class Main {
private static final int maxn = 50050;
private static long[] sum = new long[maxn<<2];
private static long[] a = new long[maxn];
private static void pushup(int rt) {
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
private static void build(int l, int r, int rt) {
if(l == r) {
sum[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt<<1);
build(mid+1, r, rt<<1|1);
pushup(rt);
}
private static void add(int pos, long value, int l, int r, int rt) {
if(l == r) {
sum[rt] += value;
return;
}
int mid = (l+r) >> 1;
if(pos <= mid) add(pos, value, l, mid , rt<<1);
else add(pos, value, mid+1, r, rt<<1|1);
pushup(rt);
}
private static long query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) return sum[rt];
int mid = (l + r) >> 1;
long ans = 0;
if(L <= mid) ans += query(L, R, l, mid, rt<<1);
if(R > mid) ans += query(L, R, mid+1, r, rt<<1|1);
return ans;
}
public static void main(String[] args) throws IOException {
int T, n, cas = 1;
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
T = (int)in.nval;
while(T > 0) {
T --;
out.println("Case " + cas + ":");
cas ++;
in.nextToken();
n = (int)in.nval;
for(int i=1;i<=n;i++) {
in.nextToken();
a[i] = (long)in.nval;
}
build(1, n, 1);
while(true) {
in.nextToken();
String order = (String)in.sval;
if(order.equals("End")) break;
else if(order.equals("Query")) {
in.nextToken();
int L = (int)in.nval;
in.nextToken();
int R = (int)in.nval;
long ans = query(L, R, 1, n, 1);
out.println(ans);
} else if(order.equals("Add")) {
in.nextToken();
int pos = (int)in.nval;
in.nextToken();
long val = (long)in.nval;
add(pos, val, 1, n, 1);
} else if(order.equals("Sub")) {
in.nextToken();
int pos = (int)in.nval;
in.nextToken();
long val = -(long)in.nval;
add(pos, val, 1, n, 1);
}
}
}
out.flush();
}
}
posted on 2015-03-26 08:19
marchalex 閱讀(474)
評(píng)論(0) 編輯 收藏 所屬分類(lèi):
java小程序