线段树(Segment Tree)的组成
以下出现的k为线段树内代表区间的点的编号
数据
- 点的个数 n
- 该点代表的区间各数之和 sum[4*maxn]
- 该点代表的区间上改变的量 add[4*maxn]
sum[k] 和 add[k] 的 区分
比如说 ， k代表的区间上每个数都加上num,
则变化后的sum[k] = sum[k] + (区间长度) * num
且变化后的add[k] = add[k] + num
函数
建树
- 目标：得到所有区间的sum[k]
- 过程：分治递归区间。
递归终止：区间内只含有一个数，即 l == r 时 ，sum[k] = res[l] 或 res[r]
子区间递归结束后，
递归过程 sum[k] = sum[k << 1] + sum[k << 1 | 1]
- 注意
递归子区间时，两个子区间的k应分别 << 1 或 << 1 | 1(即 << 1后 + 1),
以保证对于每个区间,编号k是唯一的，且可从比它们更大的区间到达
更新区间点值
- 目标：更新涉及到的区间的sum[k] ， 并更新目标区间的add[k]
- 过程：分治递归区间。
递归终止：当前区间等价于目标区间时 ， 更新其add[k]（即 add[k] = add[k] + 要加到目标区间的值）
递归过程：
当前区间的sum[k]都必须更新(即sum[k] = sum[k] + 目标值 * 目标区间长度)
目标区间必须为当前区间的子集，
如果递归到下一层时 当前区间中点在目标区间内 而 当前区间的两端在目标区间外 ， 则应将目标区间与当前区间同时分治 ；
如果递归到下一层时 当前区间中点在目标区间外 ，
若目标区间完全为 当前区间左端点 到 当前区间中点 之间区间 的子集 ， 则只在这个新区间更新 ；
若目标区间完全为 当前区间中点 到 当前区间右端点 之间区间 的子集 ， 则只在这个新区间更新 。
查询区间和
- 目标 ：获得目标区间的sum[k]和 包含目标区间的父区间的add[k] 与 目标区间长度 的 乘积 的 加和
- 过程：依旧是分治递归区间。
递归终止：当前区间等价于目标区间时 ，返回其sum[k] 及 一路下来父区间的add[k']之和 与 目标区间长度 的 乘积 的 加和
递归过程 ：
将当前区间的add[k]加入下一层查询的参数中
与 “更新区间点值 -> 过程 -> 递归过程 2.” 大同小异
其他
- 快读快写之类的常数优化不再赘述
线段树(Segment Tree)的代码
C++98/03
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
typedef long long ll;
ll read();
const ll MAXN = ll(4e6) + 40;
ll n,m,sum[MAXN],add[MAXN],res[MAXN / 4];
void build(ll,ll,ll);//建树
void update(ll,ll,ll,ll,ll,ll);//更新区间点值
ll query_sum(ll,ll,ll,ll,ll,ll);//查询区间和
int main()
{
n = read(); m = read();
for(ll t = 1 ; t <= n ; ++t ){
res[t] = read();
}
build(1,1,n);
for(ll t = 1 ; t <= m ; ++t ){
ll opCode,x,y,k;
opCode = read();
x = read(); y = read();
if(opCode == 1){
k = read();
update(1,1,n,x,y,k);
}else if (opCode == 2){
printf("%lld
",query_sum(1,1,n,x,y,0));
}
}
return 0;
}
ll query_sum(ll k , ll l , ll r , ll x , ll y , ll v ){
if(x == l && y == r){
return sum[k] + (r - l + 1) * v;
}
ll mid = ( l + r ) >> 1 ;
if(y <= mid)
return query_sum(k << 1 , l , mid , x , y , v + add[k] );
else if(x >= mid + 1 )
return query_sum(k << 1 | 1 , mid + 1 , r , x , y ,v + add[k]);
return
query_sum(k << 1 , l ,mid , x , mid , v + add[k])
+
query_sum(k << 1 | 1 , mid + 1 , r ,mid + 1 , y , v + add[k]);
}
void update(ll k, ll l , ll r , ll x , ll y , ll v ){
sum[k] += v * (y - x + 1);
if(l == x && r == y){
add[k] += v;
return;
}
ll mid = (l + r) >> 1;
if(y <= mid)
update(k << 1 , l , mid , x , y , v );
else{
if(x > mid)
update(k << 1 | 1 , mid + 1 , r , x , y , v);
else
update(k << 1 , l , mid , x , mid , v),
update(k << 1 | 1 , mid + 1 , r , mid + 1 , y , v );
}
}
void build(ll k , ll l ,ll r){
if(l == r){
sum[k] = res[(l+r) >> 1];
return;
}
ll mid = (l + r) >> 1;
build(k << 1 , l , mid);
build(k << 1 | 1 , mid + 1, r);
sum[k] = sum[k << 1] + sum[k << 1 | 1];
}
ll read()
{
ll ans = 0 , mark = 1; char c = getchar();
while(c < '0' || c > '9'){
if(c == '-')
mark = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
ans = ans * 10 + c -'0';
c = getchar();
}
return ans * mark;
}