<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
树状数组
相信看到“将$l$到$r$之间的数值全部加上$d$”这种需求,绝大多数了解过线段树的都会第一时间往线段树上想,那么如果用线段树成功解决了这个问题,应该会发现线段树最根本的弊端就是占用空间太大,存储树结构的线性表需要构造的长度是给定序列长度的4倍,树节点也需要分别构造,而且线段树类主要的几个成员函数都是递归的,这些都会隐性增加程序执行时间
那么有没有更好的办法呢?可以想到的是,在基础篇的 差分 问题中,曾经就处理过多次区段整体更新之后输出序列中每一个值的需求,那么以差分序列作为树状数组的数据源,就可以将区段整体的更新对应为区段两端点的单个位置更新,把每个位置的值对应为树状数组的前缀和,就完美的和一般的树状数组串起来了
原理用下面的一张图表示,细节见注释,主要是介绍树状数组类的声明与实现,线段树类另附
C++ 代码
树状数组类:
class BinaryIndexedTree {
private:
//base是树状数组序列,arr是原序列
vector<ll> base, arr;
//另外存放树状数组的长度,base和arr的长度不一定等于输入序列的长度
int length = 0;
//lowbit指的是一个数二进制表示下最低位的1所代表的值,相当于一个数的二进制划分中最小的一部分
ll lowbit(int x) {
return x & -x;
}
//单个位置的更新
void _update(int id, int x) {
//向上更新每个前驱节点i + lowbit(i)
for (int i = id; i <= length; i += lowbit(i)) {
base[i] += x;
}
}
ll _query(int id) {
ll sum = 0;
//对下标做二进制划分,减少lowbit(i)其实就是划分出了长度最小的一段
for (int i = id; i >= 1; i -= lowbit(i)) {
sum += base[i];
}
return sum;
}
public:
BinaryIndexedTree(int n) {
length = n;
//差分序列,前后最好都留点冗余
base.resize(n + 2);
arr.resize(n + 2);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
//下标为i的位置按照差分序列的值去构造
_update(i, arr[i] - arr[i - 1]);
}
}
//区段[l,r]整体更新转化为l,r+1两个位置的单个更新
void update(int l, int r, int x) {
_update(l, x);
_update(r + 1, -x);
}
//既然是树状“数组”,那么取得某一下标处的元素,最好要跟普通数组保持一致,因此重载了下标运算符
ll operator[](int id) {
//对差分序列的[0,id]区段求前缀和,就是下标id位置的真值
return _query(id);
}
};
线段树类:
//线段树节点的结构体
struct STNode
{
//代表区段的左右端点
int left, right;
//sum指的是区段内所有元素的累加和
//offset就是lazyTag,其实际含义为区段整体偏离原值的程度,即“偏移量”,由于其延迟加载特性,得名“懒”标记
ll sum, offset;
STNode() :left(0), right(0), sum(0ll), offset(0ll) {}
STNode(int l, int r, ll s) :left(l), right(r), sum(s), offset(0) {}
};
class SegmentTree
{
private:
vector<int> arr;
vector<STNode> base;
//递归初始化线段树
void buildTree(int p, int l, int r)
{
//只有l==r时arr[l]才有意义
base[p] = STNode(l, r, (ll)arr[l]);
if (l == r) return;
int m = l + r >> 1;
//二分区段,分别构造
buildTree(2 * p, l, m);
buildTree(2 * p + 1, m + 1, r);
//将两半区段向上累加
base[p].sum = base[2 * p].sum + base[2 * p + 1].sum;
}
void _update(int p, int l, int r, ll k)
{
//是被待更新区段包含在内的区段,更新此节点的sum和offset
if (base[p].left >= l && base[p].right <= r)
{
base[p].sum += k * (base[p].right - base[p].left + 1);
base[p].offset += k;
return;
}
//未被包含,如果有offset要向下传递
pushDown(p);
//二分该节点对应区段,两分区满足更新条件才能更新
int m = base[p].left + base[p].right >> 1;
if (l <= m) _update(2 * p, l, r, k);
if (r > m) _update(2 * p + 1, l, r, k);
//一样要向上传递累加和
base[p].sum = base[2 * p].sum + base[2 * p + 1].sum;
}
ll _query(int p, int l, int r)
{
//类似于_update,只是不需要向上传递sum了
if (base[p].left >= l && base[p].right <= r) return base[p].sum;
pushDown(p);
int m = base[p].left + base[p].right >> 1;
ll ans = 0ll;
if (l <= m) ans += _query(2 * p, l, r);
if (r > m) ans += _query(2 * p + 1, l, r);
return ans;
}
void pushDown(int p)
{
if (base[p].offset != 0)
{
auto ofs = base[p].offset;
//更新后继节点的offset的同时,sum也要更新,更新完之后当前节点offset归零
base[2 * p].sum += ofs * (base[2 * p].right - base[2 * p].left + 1);
base[2 * p + 1].sum += ofs * (base[2 * p + 1].right - base[2 * p + 1].left + 1);
base[2 * p].offset += ofs;
base[2 * p + 1].offset += ofs;
base[p].offset = 0ll;
}
}
public:
SegmentTree(vector<int>& v)
{
int len = v.size();
//arr,base的长度都是输入序列的4倍
arr.resize(10 + (len << 2));
base.resize(10 + (len << 2));
copy(v.begin(), v.end(), arr.begin() + 1);
buildTree(1, 1, len);
}
//直接修改区段整体
void update(int l, int r, ll k)
{
_update(1, l, r, k);
}
//把单个位置id上的值看成[id,id]区段的累加和,只不过区段的长度是1
ll operator[](int id)
{
return _query(1, id, id);
}
};