洛谷 P3374 【模板】树状数组 1（线段树解法）

【题目链接】

洛谷 P3374 【模板】树状数组 1

【题目考点】

1. 线段树

线段树(Segment tree)是一种用来维护区间信息的数据结构。
线段树中每个结点代表一个区间
根结点代表整体区间。
叶子结点代表长为1的单位区间。
对于线段树中的每一个分支结点$[l,r]$，m=(l+r)/2

• 左孩子表示的区间为$[l,m]$
• 右孩子表示的区间为$[m+1,r]$

线段树的设计思想为：分治思想

线段树的性质有：

1. 线段树是平衡二叉树
2. 线段树除去最后一层，是满二叉树。
3. 区间长度为n的线段树的叶子结点数量为n。
4. 区间长度为n的线段树的总结点数量为$2n-1$。
5. 任意两个结点或是包含关系，或者没有重叠部分。
6. 区间长度为n的线段树的高度为$\lceil {\log }_{2}n\rceil +1$。
7. 用顺序存储结构存储区间长为n的线段树，需要数组长度不超过4n-1。因此常把数组长度设为4n。
8. 任意长为L的子区间都可以被分成不超过$2{\log }_{2}L$个由线段树中结点表示的区间。

以上各性质的证明见：线段树相关性质证明

【解题思路】

首先线段树每个结点需要包含该结点表示的区间$[l,r]$，以及需要维护的该区间的加和。
使用树的顺序存储结构来保存线段树，表示线段树的数组是tree。
根据性质7，序列长度最大为$N$时，数组长度需要开到$4N$。

struct Node
{int l, r;//当前结点表示区间[l, r]long long val;//区间[l, r]的加和为val
} tree[4*N];

在树的顺序存储结构中，结点地址即为tree数组的下标。地址为$i$的结点的左孩子的地址为$2i$，右孩子的地址为$2i+1$。
pushUp操作为使用孩子结点的值更新当前结点的值。本题中，孩子结点区间和的加和为当前结点表示的区间和。

void pushUp(int i)//更新地址为i的结点的值
{tree[i].val = tree[2*i].val+tree[2*i+1].val;
}

1. 建树

首先将数值序列输入到数组a。根据a序列建立线段树。
在建树过程中需要设置树中各个结点的区间、数值。
基本过程为：
先设置当前结点表示的区间。
如果当前结点为叶子结点，则设置该结点的值。
如果不是叶子结点，则先递归建立左子树，再递归建立右子树。
而后根据左右孩子的值确定当前结点的值。
建树的过程即为对线段树遍历的过程，根据性质4，线段树中总结点数量为$2n-1$，因此建树操作的时间复杂度为$O(n)$。

void build(int i, int l, int r)//构建根结点地址为i的表示区间[l, r]的线段树
{tree[i].l = l, tree[r].r = r;//设结点表示的区间if(l == r)//如果区间长度为1，该结点为叶子结点{tree[i].val = a[l];//原序列为a序列return;}int mid = (l+r)/2;build(2*i, l, mid);//递归构建左右子树build(2*i+1, mid+1, r);pushUp(i);//更新地址为i的结点的值
}

2. 单点修改

要使a序列中第x元素的值增加v，即完成a[x] += v，考虑线段树的变化。
首先在线段树中递归找到表示第x位置元素的叶子结点，将该结点的值修改，再不断向上回溯，回溯时使用孩子的值更新当前结点的值。
单点修改的函数递归调用次数与线段树高度成正比。根据性质6，线段树的高度为$O(\log n)$量级，因此线段树的单点修改操作的时间复杂度为$O(\log n)$。

void update(int i, int x, long long v)//在根结点地址为i的线段树中，进行单点修改a[x] += v
{if(x < tree[i].l || x > tree[i].r) return;if(tree[i].l == tree[i].r)//如果i是叶子结点   {tree[i].val += v;return;}update(2*i, x, v);   update(2*i+1, x, v);pushUp(i);//更新地址为i的结点的值
}

3. 区间查询

要查询a序列给定区间$[l,r]$中元素的加和，要做的是将$[l,r]$区间划分为几个线段树中结点表示的区间，将这些区间的值加和。
要在某结点表示的区间中，返回$[l,r]$中元素的加和：
首先判断当前结点表示的区间和$[l,r]$是否有交集。如果没有交集则返回。
如果当前结点表示的区间完全被区间$[l,r]$包含，则返回当前结点的值。
否则分别求出当前结点的两个子结点表示的区间中的且在$[l,r]$中的元素的加和，将二者的加和返回。
每找到一个完全被$[l,r]$包含的区间就返回。设$L=r-l+1$，而$L$最大可以达到$n$。根据性质8，可知这样的区间有$2{\log }_{2}L$个，是$O(\log n)$量级。区间查询访问到的结点构成了线段树的一个子树，该子树的叶子结点表示的就是区间$[l,r]$被线段树划分成的各个区间。
该树的叶子结点数是$O(\log n)$的。
对于该树中度为1的结点，只有“左孩子表示的区间在$[l,r]$外，右孩子表示的区间在$[l,r]$内”，或“右孩子表示的区间在$[l,r]$外，左孩子表示的区间在$[l,r]$内”，只能最多在二叉树的左右两侧形成两条链，每条链的最大高度为$O(\log n)$。

long long query(int i, int l, int r)
{//在根结点地址为i的线段树中，查询区间[l, r]中所有元素的和if(tree[i].r < l || tree[i].l > r)return 0; if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;return query(2*i, l, r) + query(2*i+1, l, r);
}

【题解代码】

#include<bits/stdc++.h>
using namespace std;
#define N 500005
struct Node
{int val, l, r;
} tree[4*N];
int n, m, a[N];
void pushUp(int i)//更新tree[i]的值 
{tree[i].val = tree[2*i].val+tree[2*i+1].val;
}
void build(int i, int l, int r)//建树 O(n)
{tree[i].l = l, tree[i].r = r;if(l == r){tree[i].val = a[l];return;}int mid = (l+r)/2;build(2*i, l, mid);build(2*i+1, mid+1, r);pushUp(i);
}
void update(int i, int x, int v)//单点修改：a[x] += v O(logn)
{if(x < tree[i].l || x > tree[i].r)return;if(tree[i].l == tree[i].r){tree[i].val += v;return;}update(2*i, x, v);update(2*i+1, x, v);pushUp(i);
} 
int query(int i, int l, int r)//区间查询：a[l]+...+a[r] O(logn) 
{if(tree[i].r < l || tree[i].l > r)return 0;if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;return query(2*i, l, r)+query(2*i+1, l, r);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int op, x, k, y;cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> a[i];build(1, 1, n);for(int i = 1; i <= m; ++i){cin >> op;if(op == 1){cin >> x >> k;update(1, x, k);} else{cin >> x >> y;cout << query(1, x, y) << '\n';}}return 0;
}