线段树（区间求和，区间加，单点更新等）
线段树
线段树是一种二叉搜索树。它将一段区间划分为若干个单位区间，每一个节点都储存着一个区间。
线段树可做 区间求和，区间最值，区间更新，单点更新等操作
以区间和为例来做介绍：
建树
const int maxn=1000000+5;
struct Tree{
int l,r;
int val;
int lazy,tag;//标记，需要区间更新时使用
}tree[maxn*2];
//把子节点的信息汇总到了父节点上，根据题目要求可做修改，比如可以更改为区间最值
void pushup(int cur)
{
tree[cur].val = tree[2 * cur].val + tree[2 * cur + 1].val;
//父节点是两个子节点的和，一直往上传值，就能使根节点是所有节点的和
}
void build(int l,int r,int step)
{
int mid=(l+r)/2;
tree[step].val=0; //对节点初始化赋值，视情况看赋多少
tree[step].l=l;
tree[step].r=r;
if(l==r){ //到达叶子节点
tree[step].val=ary[l]; //赋值，这一步是对叶子节点的更新，若无需更新，则可以不写
//ary数组为元素的初始值
return;
}
//如果不是叶节点，就一直左右递归找，直到找到为止
build(l,mid,step*2);
build(mid+1,r,step*2+1);
//将子节点的值汇总给父亲节点，用于求和
pushup(step);
}
单点更新 hdu-1166
//单点值的更改，找指定的叶节点
//将tar节点的值增加val
void update(int tar, int val, int step)
{
int l = tree[step].l, r = tree[step].r;
if (l == r)
{
tree[step].val = tree[step].val + val;//节点更新，此处为增加，也可做换值处理
return;
}
int mid = (l + r) / 2;
if (tar <= mid)
update(tar, val, 2 * step);
else
update(tar, val, 2 * step + 1);
pushup(step);
}
区间更新
/************************************** poj-3468 ***************************************/
//区间加
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100000 + 5
long long a[MAXN];
struct Tree{
int left;
int right;
long long sum;
long long lazy;
}tree[MAXN << 2];
//把子节点汇集到父节点
void push_up(int step)
{
tree[step].sum = tree[step << 1].sum + tree[step << 1 | 1].sum;
}
//区间加后向下更新
void push_down(int step)
{
if (tree[step].lazy){
tree[step << 1].sum += (tree[step << 1].right - tree[step << 1].left + 1)*tree[step].lazy;
tree[step << 1 | 1].sum += (tree[step << 1 | 1].right - tree[step << 1 | 1].left + 1)*tree[step].lazy;
tree[step << 1].lazy += tree[step].lazy;
tree[step << 1 | 1].lazy += tree[step].lazy;
tree[step].lazy = 0;
}
}
void BuildTree(int step, int l, int r)
{
tree[step].left = l;
tree[step].right = r;
tree[step].sum = 0;
if (l == r)
tree[step].sum = a[l];
else{
int mid = (l + r) >> 1;
BuildTree(step << 1, l, mid);
BuildTree(step << 1 | 1, mid + 1, r);
push_up(step);
}
return;
}
long long query(int step, int l, int r){
if (tree[step].left == l && tree[step].right == r)
return tree[step].sum;
push_down(step);
int mid = (tree[step].left + tree[step].right) >> 1;
if (r <= mid)
return query(step << 1, l, r);
else if (l > mid)
return query(step << 1 | 1, l, r);
else
return query(step << 1, l, mid) + query(step << 1 | 1, mid + 1, r);
}
void u_update(int step, int l, int r, int val)
{
if (tree[step].left == l && tree[step].right == r){
tree[step].sum += 1LL * (r - l + 1)*val;
tree[step].lazy += val;
return;
}
else{
int mid = (tree[step].left + tree[step].right) >> 1;
push_down(step);
if (r <= mid)
u_update(step << 1, l, r, val);
else if (l > mid)
u_update(step << 1 | 1, l, r, val);
else {
u_update(step << 1, l, mid, val);
u_update(step << 1 | 1, mid + 1, r, val);
}
push_up(step);
}
return;
}
int main()
{
int n, m;
int i;
int l, r, val;
char op[20];
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
scanf("%lld", &a[i]);
BuildTree(1, 1, n);
while (m--){
scanf("%s", op);
if (op[0] == 'Q'){
scanf("%d%d", &l, &r);
printf("%lld\n", query(1, l, r));
}
else{
scanf("%d%d%d", &l, &r, &val);
u_update(1, l, r, val);
}
}
return 0;
}
/******************************** hdu 1698 *************************************/
//将[l,r]区间内的值更换为val，需要用到标记
#include<stdio.h>
const int maxn = 10000000 + 5;
struct Tree {
int l, r;
int val;
}tree[maxn];
void build(int l, int r, int step)
{
tree[step].l = l;
tree[step].r = r;
tree[step].val = 1;
if (l == r)
return;
int mid = (l + r) / 2;
build(l, mid, step * 2);
build(mid + 1, r, step * 2 + 1);
}
void update(int l, int r, int val, int step)
{
if (tree[step].l == l && tree[step].r == r) {
tree[step].val = val;
return;
}
if (tree[step].val != -1) {
tree[step * 2].val = tree[step * 2 + 1].val = tree[step].val;
tree[step].val = -1;
}
int mid = (tree[step].l + tree[step].r) / 2;
if (r <= mid)
update(l, r, val, step * 2);
else if (l > mid)
update(l, r, val, step * 2 + 1);
else {
update(l, mid, val, step * 2);
update(mid + 1, r, val, step * 2 + 1);
}
}
int query(int step)
{
if (tree[step].val != -1)
return (tree[step].r - tree[step].l + 1)*tree[step].val;
else
return query(step * 2) + query(step * 2 + 1);
}
int main()
{
int t;
scanf("%d", &t);
for (int i = 1; i <= t; i++) {
int n;
scanf("%d", &n);
build(1, n, 1);
int m;
scanf("%d", &m);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
update(a, b, c, 1);
}
printf("Case %d: The total value of the hook is %d.\n", i, query(1));
}
}
区间查询
//查询区间[ql,qr]里面元素的总和
int query(int ql,int qr,int cur)
{
int l=tree[cur].l,r=tree[cur].r;
if(ql<=l&&qr>=r)
return tree[cur].val;
int mid=(l+r)/2,res=0;
if(ql<=mid)
res+=query(ql,qr,2*cur);
if(qr>mid)
res+=query(ql,qr,2*cur+1);
return res;
}
线段树的动态开点
**用处:**一般线段树开局直接4*N的空间，然而当N很大时，4倍空间会消耗很多，这时考虑用动态开点线段树，用多少开多少，跟c++的new差不多
**预备：**一个根节点root,存值数组c[N],左右儿子 lc[N],rc[N]
算法流程：
1.一开始只有一个根节点
2.update操作:类似串算法，每次传入节点root,区间范围[l,r]和更新点x,判断x在区间的哪边，在哪边就就往哪边走，如果遇到一个无标记的节点但又需要往这个节点走
就以访问次序给这个节点标号，像正常线段树更新即可。
3.query操作:和一般线段树不同的是，当我们遇到一个没有访问过的节点，直接返回，其他与线段树查询一致。
假设我们要对 1 3 5 7 8 9这段序列操作，区间范围[1,9] 开的线段树如下可以少点2,4,6这3个儿子节点
如果这段区间没有5，我们甚至可以不用开7号和8号节点
poj 2299
//以求逆序对为例
#include <iostream>
#include <algorithm>
#include <cmath>
#include<string.h>
using namespace std;
const int N = 5e6 + 10;
int root, n, c[N], lc[N], rc[N], cnt;
void update(int &p, int l, int r, int x, int val)
{
if (!p) p = ++cnt; //遇到了，但没标号，标记
if (l == r)
{
c[p] += val;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) update(lc[p], l, mid, x, val);
else update(rc[p], mid + 1, r, x, val);
c[p] = c[lc[p]] + c[rc[p]];
}
int query(int p, int l, int r, int x, int y)
{
if (!p) return 0;
if (l == x && r == y) return c[p];
int mid = (l + r) >> 1;
if (y <= mid) return query(lc[p], l, mid, x, y);
else if (x > mid) return query(rc[p], mid + 1, r, x, y);
return query(lc[p], l, mid, x, mid) + query(rc[p], mid + 1, r, mid + 1, y);
}
int main()
{
ios::sync_with_stdio(false);
while (cin >> n && n) {
memset(c, 0, sizeof(c));
memset(rc, 0, sizeof(rc));
memset(lc, 0, sizeof(lc));
long long ans = 0;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
ans += query(root, 1, 1e9, x + 1, 1e9);
update(root, 1, 1e9, x, 1);
}
cout << ans << endl;
}
return 0;
}
投递哔哩哔哩等公司10个岗位 >
金山WPS二面19人在聊