企业官网建设流程全解析

线段树比树状数组好理解很多很多很多，主要是因为它没有那个烦人的lowbit。

线段树比树数好理解，支持的操作更多，所有操作时间复杂度一致，但代码更长，相较而言我还是选线段树。

为了防止自己忘记，我把笔记全都复制上来。

题单简介

一、线段树知识点概述

1. 线段树的基本概念

• 线段树（Segment Tree）是一种用于处理区间问题的数据结构。它可以在O(logN)的时间内完成区间查询（如区间和、区间最值等）和区间更新。
• 核心思想：将整个区间划分成若干个小区间，每个节点存储一个区间的信息。线段树是一棵完全二叉树（通常用数组存储），对于区间[1, n]，根节点表示整个区间，每个节点表示一个区间，叶子节点表示单个元素。

// 基础线段树节点（以求和为例） struct Node { int l, r; // 区间左右端点 long long sum; // 区间和 long long tag; // 懒惰标记（用于区间修改） } tree[4 * MAXN]; // 通常开4倍空间

2. 线段树的基本操作

• 建树（Build）：从根节点开始，递归地将区间分成两半，直到叶子节点，然后回溯计算每个节点的值。

void build(int p, int l, int r) { tree[p].l = l; tree[p].r = r; if (l == r) { tree[p].sum = a[l]; // 叶子节点 return; } int mid = (l + r) / 2; build(p * 2, l, mid); // 左子树 build(p * 2 + 1, mid + 1, r); // 右子树 tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum; // 向上更新 }

• 区间查询（Query）：查询一个区间的信息，通过递归地将查询区间与当前节点区间进行比较，合并子区间的查询结果。

long long query(int p, int l, int r) { if (l <= tree[p].l && tree[p].r <= r) { return tree[p].sum; // 完全包含 } push_down(p); // 查询前下传标记 int mid = (tree[p].l + tree[p].r) / 2; long long ans = 0; if (l <= mid) ans += query(p * 2, l, r); if (r > mid) ans += query(p * 2 + 1, l, r); return ans; }

• 单点更新（Update）：更新一个叶子节点的值，并递归更新其所有祖先节点。

// 将位置pos的值修改为val void update_point(int p, int pos, long long val) { // 找到叶子节点 if (tree[p].l == tree[p].r) { tree[p].sum = val; // 直接修改 return; } // 递归查找pos所在子树 int mid = (tree[p].l + tree[p].r) / 2; if (pos <= mid) { update_point(p * 2, pos, val); // 左子树 } else { update_point(p * 2 + 1, pos, val); // 右子树 } // 回溯更新父节点 tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum; }

• 区间更新（Update Range）：更新一个区间内的所有值，如果使用懒惰标记（Lazy Tag），可以优化到O(logN)。

void update(int p, int l, int r, long long val) { if (l <= tree[p].l && tree[p].r <= r) { tree[p].sum += val * (tree[p].r - tree[p].l + 1); tree[p].tag += val; // 打上懒惰标记 return; } push_down(p); // 分裂前下传标记 int mid = (tree[p].l + tree[p].r) / 2; if (l <= mid) update(p * 2, l, r, val); if (r > mid) update(p * 2 + 1, l, r, val); tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum; }

3. 懒惰标记（Lazy Propagation）

当进行区间更新时，如果每次都更新到叶子节点，时间复杂度会退化为O(N)。懒惰标记的思想是：在更新时，如果当前节点区间完全被更新区间覆盖，则只更新当前节点，并打上懒惰标记，表示该节点的子节点尚未更新。在后续查询或更新需要进入子节点时，再将懒惰标记下传。

void push_down(int p) { if (tree[p].tag) { int lc = p * 2, rc = p * 2 + 1; // 更新子节点值 tree[lc].sum += tree[p].tag * (tree[lc].r - tree[lc].l + 1); tree[rc].sum += tree[p].tag * (tree[rc].r - tree[rc].l + 1); // 下传标记 tree[lc].tag += tree[p].tag; tree[rc].tag += tree[p].tag; // 清除当前标记 tree[p].tag = 0; } }

4. 动态开点线段树

当区间范围很大（如10^9）而实际用到的节点不多时，可以使用动态开点线段树，即只在需要的时候创建节点，避免空间浪费。

5. 权值线段树与线段树合并

权值线段树：以权值为下标建立线段树，可以用于求解第k大、逆序对等问题。

struct Node { int l, r; int maxv; // 存储最大值 int tag; }; // 向上更新改为取max tree[p].maxv = max(tree[p*2].maxv, tree[p*2+1].maxv);

线段树合并：将两棵线段树合并，常用于树上问题。

struct Node { int l, r; long long sum; long long add_tag; // 加法标记 long long cov_tag; // 覆盖标记（需特殊值表示无覆盖） bool has_cov; // 是否有覆盖标记 };

6. 扫描线

用于解决平面内矩形面积并、周长并等问题。

第一阶段：线段树基础

P3374 【模板】树状数组 1 （实际上，我们可以用线段树做，但树状数组更简单，这里作为线段树的入门练习）

P3368 【模板】树状数组 2 （同样，线段树可做）

P3372 【模板】线段树 1 （区间加、区间和）

P3373 【模板】线段树 2 （区间加、乘，区间和）

注意：虽然前两题是树状数组的模板，但我们可以用线段树来实现，作为线段树单点更新和区间查询的练习。

第二阶段：区间更新与懒标记

P3372 【模板】线段树 1 （这题也是区间更新的基础）

P3373 【模板】线段树 2 （区间加和乘，懒标记传递复杂一些）

P2574 XOR的艺术 （区间异或，懒标记）

P2846 [USACO08NOV] Light Switching G （区间取反，懒标记）

第三阶段：线段树的应用与变形

P3870 [TJOI2009] 开关 （区间取反，区间和）

P4513 小白逛公园 （区间最大子段和）

P1471 方差 （区间平均数，区间方差）

P1531 I Hate It （区间最大值，单点更新）

P1558 色板游戏 （区间覆盖，查询区间颜色数，状态压缩）

P1438 无聊的数列 （区间等差数列更新，区间查询）

P1253 扶苏的问题 （区间加，区间赋值，区间查询最大值）

P4145 上帝造题的七分钟2 / 花神游历各国 （区间开方，区间和）

第四阶段：综合练习与提高

P2572 [SCOI2010] 序列操作 （多种操作：赋值、取反、区间和、区间连续1的个数）

P4344 [SHOI2015] 脑洞治疗仪 （区间赋值，区间合并）

P6327 区间加区间sin和 （利用三角函数和差公式）

P3285 [SCOI2014] 方伯伯的OJ （线段树+平衡树，较难）

P4080 [SDOI2016] 储能表 （线段树+数位DP，较难）

注：单点查询很没有必要，update中l==r即可。

依旧模板写法：

#include <bits/stdc++.h> using namespace std; const long long maxn=5e5+10; struct node{ int l,r; long long sum; long long tag; }; node tree[4*maxn]; long long a[maxn+1]; void build(int p,int l,int r){ tree[p].l=l; tree[p].r=r; tree[p].sum=0; tree[p].tag=0; if(l==r){ tree[p].sum=a[l]; return; } int mid=(l+r)/2; build(2*p,l,mid); build(2*p+1,mid+1,r); tree[p].sum=tree[p*2].sum+tree[p*2+1].sum; } void pushdown(int p){ if(tree[p].tag==0) return; int lk=p*2,rk=p*2+1; tree[lk].tag+=tree[p].tag; tree[rk].tag+=tree[p].tag; tree[lk].sum+=tree[p].tag*(tree[lk].r-tree[lk].l+1); tree[rk].sum+=tree[p].tag*(tree[rk].r-tree[rk].l+1); tree[p].tag=0; } long long query(int p,int l,int r){ if(l<=tree[p].l and r>=tree[p].r){ return tree[p].sum; } pushdown(p); int mid=(tree[p].l+tree[p].r)/2; long long ans=0; if(l<=mid) ans+=query(p*2,l,r); if(r>mid) ans+=query(p*2+1,l,r); return ans; } void update(int p,int l,int r,long long val){ if(l<=tree[p].l and r>=tree[p].r){ tree[p].sum+=val*(tree[p].r-tree[p].l+1); tree[p].tag+=val; return; } pushdown(p); int mid=(tree[p].l+tree[p].r)/2; if(l<=mid) update(p*2,l,r,val); if(r>mid) update(p*2+1,l,r,val); tree[p].sum=tree[p*2].sum+tree[p*2+1].sum; } void adddate(int p,int l,int r,long long val){ if(l<=tree[p].l and r>=tree[p].r){ tree[p].sum+=val*(tree[p].r-tree[p].l+1); tree[p].tag+=val; return; } pushdown(p); int mid=(tree[p].l+tree[p].r)/2; if(l<=mid) update(p*2,l,r,val); if(r>mid) update(p*2+1,l,r,val); tree[p].sum=tree[p*2].sum+tree[p*2+1].sum; } int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); for(int cnt=1;cnt<=m;cnt++){ int mod; cin>>mod; if(mod==1){ long long x,y,k; cin>>x>>y>>k; update(1,x,y,k); } if(mod==2){ long long x,y; cin>>x>>y; cout<<query(1,x,y)<<endl; } } }

模板题在此，模板写法完全可以过，而且模板写法支持的不止模板题。

P3372 【模板】线段树 1

题目描述

如题，已知一个数列 {ai​}，你需要进行下面两种操作：

1. 将某区间每一个数加上 k。
2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 n,m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数 ai​，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：

1. 1 x y k：将区间 [x,y] 内每个数加上 k。
2. 2 x y：输出区间 [x,y] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例

输入 #1复制

5 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4

输出 #1复制

11 8 20

说明/提示

对于 15% 的数据：n≤8，m≤10。
对于 35% 的数据：n≤103，m≤104。
对于 100% 的数据：1≤n,m≤105，ai​,k 为正数，且任意时刻数列的和不超过 2×1018。

【样例解释】

今天说实话听的比较水，一是因为老师为了其他同学讲的真的有点过于详细了，有点啰嗦；而是因为我在研究天才白讲的向量。。。向未来的自己道个歉。（虽然我觉得今天学到的比认真听课多）