線段樹題，本題對線段樹的操作有建樹（MakeTree()）、查找（Query()）、更新（update()）。
建樹一次完成，時間花費為O(LogN)；查詢的時間復雜度鄙人還不會分析O(∩_∩)O~，最壞可能是O(N)，不過這種情況應該很難出現；更新的算法值得商榷，不同的策略時間復雜度會相差很大。下面講解兩種比較用以想到的更新策略。
更新方法一：
每次都將所有能更新的節點更新，這種方式最壞情況下將會更新樹中所有節點，此時時間復雜度為O(N)。本題使用這種方法會TLE。
更新方法二：
每次都盡量少的更新節點信息，與第一種方法相比，Node內會多一個變量en，我把它形象的稱之為“勢能”，計算結果時要將該的所有父節點的“勢能”也考慮在內。這種方法的時間復雜度也不好分析，但明顯優于第一種方法。
這一題對時間卡的很緊，主要是花在樹的更新上。
關于線段樹可以先參閱：
http://www.shnenglu.com/hoolee/archive/2012/07/29/185531.html以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#define LEN 100010
#define LEN0 6550000
typedef struct
{
int a, b;
int l, r;
long long sum;//記錄該區間內的部分和
long long en;//記錄該節點“勢能”。
}Node;
int count;
Node A[LEN0];
int allNum[LEN];
void MakeTree(int i)
{
A[i].en = 0;
int a = A[i].a;
int b = A[i].b;
int mid = (a + b) / 2;
if(a == b)
{
A[i].sum = allNum[a];
return;
}
int l = ++count;
int r = ++count;
A[l].a = a;
A[l].b = mid;
A[r].a = mid + 1;
A[r].b = b;
MakeTree(l);
MakeTree(r);
A[i].sum = A[l].sum + A[r].sum;
A[i].l = l;
A[i].r = r;
}
long long Query(int t, int aa, int bb, long long en)
{
int a = A[t].a;
int b = A[t].b;
if(a == aa && b == bb)//1
{
return A[t].sum + en * (bb - aa + 1);
}
int mid = (a + b) / 2;
if(bb <= mid)//2
return Query(A[t].l, aa, bb, en + A[t].en);
if(aa >= mid + 1)//3
return Query(A[t].r, aa, bb, en + A[t].en);
long long suml = Query(A[t].l, aa, mid, en + A[t].en);//4
long long sumr = Query(A[t].r, mid + 1, bb, en + A[t].en);
return suml + sumr;
}
void Update(int t, int aa, int bb, int c)
{
int a = A[t].a;
int b = A[t].b;
int mid = (a + b) / 2;
int l = A[t].l;
int r = A[t].r;
A[t].sum += (bb - aa + 1) * c;
if(aa == a && bb == b)
{
A[t].en += c;
return;
}
if(bb <= mid)
Update(l, aa, bb, c);
else if(aa >= mid + 1)
Update(r, aa, bb, c);
else
{
Update(l, aa, mid, c);
Update(r, mid + 1, bb, c);
}
}
int main()
{
int i, j;
int N, Q;
int a, b, c;
scanf("%d%d", &N, &Q);
for(i = 1; i <= N; i++)
scanf("%d", &allNum[i]);
count = 0;
int t = ++count;
A[t].a = 1;
A[t].b = N;
MakeTree(t);
char str[50];
getchar();
for(i = 0; i < Q; i++)
{
gets(str);
if(str[0] == 'Q')
{
sscanf(&str[1], "%d%d", &a, &b);
long long sum = Query(1, a, b, 0);
printf("%lld\n", sum);
}
else if(str[0] == 'C')
{
sscanf(&str[1], "%d%d%d", &a, &b, &c);
Update(1, a, b, c);
}
}
//system("pause");
}posted on 2012-07-31 20:40
小鼠標 閱讀(3637)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構