线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。线段树可以在 O(\log_{2}{N}) 的时间复杂度内实现单点修改、区间修改、区间查询等操作。
为数组(假设下标从 1 开始):
构造线段树如下图(采用堆式存储):
上述数组 D 用来保存线段树,由于采用的是堆式存储,因此 D[i] 的左右孩子结点分别为 D[2\times i],D[2 \times i + 1]。不难发现上图有两种结点,银色结点括号表示该结点包含的数组 a 的区间,D[i] 的值表示 \sum_{k=i}^{j}a[k]。且若区间两端点相等为 [k,k] 则 D[i] = a[k] 即值为绿色结点。
由于树树递归定义的,因此其建立也是递归的:
void buildST(int left, int right, int p, vector<int>& D, vector<int> & a)
{if(left == right)
{D[p] = a[left];
return;
}
int mid = left + (right - left)/2;
build(left, mid, p*2, D, a);
build(mid+1, right, p*2+1, D, a);
D[p] = D[p * 2] + D[p * 2 + 1];
}
// [left,right] 为待查区间,[cl,cr] 为当前区间,p 为当前节点编号,D 为线段树的存储数组
int getSum(int left, int right, int cl, int cr, int p, vector<int> &D)
{if(left <= cl && cr <= right) // 当前区间为待查区间的子集
return D[p];
// 划分区间,递归查询
int mid = cl + (cr - cl)/2, sum = 0;
if(left <= mid) // 与左区间有交集
sum += getSum(left, right, cl, mid, p * 2, D);
if(right > mid) // 与右区间有交集
sum += getSum(left, right, mid+1, cr, p * 2 + 1, D);
return sum;
}
[cl,cr] 为当前区间,index 为要修改的数组 a 的下标,val 为修改的最终值,p 为当前节点编号。
void updateST(int cl, int cr, int index, int val, int p, vector<int>& D,vector<int>& a)
{if(cl == cr)
{a[index] = val;
D[p] = val;
return;
}
else
{int mid = cl + (cr - cl)/2;
if(index >= cl && index <= mid)
updateST(cl, mid, index, val, p * 2, D, a);
else if(index > mid && index <= cr)
updateST(mid + 1, cr, index, val, p * 2 + 1, D, a);
D[p] = D[p * 2] + D[p * 2 + 1];
}
}
此时如果将 a[1] 改成 6 , 则树变成 (红色表示有修改的节点):
int main()
{vector<int> D(10,0);
vector<int> a(6);
for(int i = 0; i < a.size();i++)
a[i] = i;
cout << "Building STree:" << endl;
buildST(1, 5, 1, D, a);
cout << "STree:";
for(int i = 1;i < D.size();i++)
cout << D[i] << " ";
cout << endl;
cout << "================================" << endl;
cout << "Quary:(1,3)"<< endl;
cout << getSum(1,3,1,5,1,D) << endl;
cout << "================================" << endl;
cout << "Update: a[1] = 6" << endl;
updateST(1,5,1,6,1,D,a);
cout << "STree:";
for(int i = 1;i < D.size();i++)
cout << D[i] << " ";
cout << endl;
cout << "================================" << endl;
cout << "Quary:(1,3)"<< endl;
cout << getSum(1,3,1,5,1,D) << endl;
}