线段树题，本题对线段树的操作有建树（MakeTree()）、查找（Query()）、更新（update()）。
建树一次完成，时间花费为O(LogN)；查询的时间复杂度鄙人还不会分析O(∩_∩)O~，最坏可能是O(N)，不过这种情况应该很难出现；更新的算法值得商榷，不同的策略时间复杂度会相差很大。下面讲解两种比较用以想到的更新策略。
更新方法一：
每次都将所有能更新的节点更新，这种方式最坏情况下将会更新树中所有节点，此时时间复杂度为O(N)。本题使用这种方法会TLE。
更新方法二：
每次都尽量少的更新节点信息，与第一种方法相比，Node内会多一个变量en，我把它形象的称之为“势能”，计算结果时要将该的所有父节点的“势能”也考虑在内。这种方法的时间复杂度也不好分析，但明显优于第一种方法。
这一题对时间卡的很紧，主要是花在树的更新上。
关于线段树可以先参阅：
http://www.cppblog.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
小鼠标 阅读(3618)
评论(0) 编辑 收藏 引用 所属分类:
数据结构