线段树与树状数组

线段树

参考C02【模板】线段树+懒标记 Luogu P3372 线段树 1 - 董晓 - 博客园

结构：叶子节点存储元素本身，非叶子节点存储元素统计值

遍历方式：先根遍历

1. 节点数组tr[N*4]

• l, r：当前节点管理的区间范围 [l, r]。
• sum：区间 [l, r] 内所有元素的和。
• add：懒标记，记录未下传的区间增量。

1. 递归建树build

   • 初始化叶子节点（l == r）的 sum 为 w[l]。

   • 非叶子节点递归构建左右子树，并通过 pushup 计算父节点的 sum。

2. 区间修改change

   • 懒标记：若当前节点区间被完全覆盖，直接更新 sum`并打标记，避免递归到底。
   • 标记下传：在访问子节点前调用 pushdown，确保之前的修改生效。

3. 区间查询query

   • 若当前节点区间完全包含于查询区间，直接返回 sum。
   • 否则下传懒标记后，递归查询左右子树并合并结果。

1. 辅助函数

   • pushup：合并子节点信息到父节点。

   • pushdown：将懒标记下传给子节点。

模板 P3372 【模板】线段树 1

// 结构体版
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define N 100005
#define LL long long
#define lc u<<1
#define rc u<<1|1
LL w[N];
struct Tree{ //线段树
  LL l,r,sum,add;
}tr[N*4];

void pushup(LL u){ //上传
  tr[u].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(LL u){ //下传
  if(tr[u].add){
    tr[lc].sum+=tr[u].add*(tr[lc].r-tr[lc].l+1),
    tr[rc].sum+=tr[u].add*(tr[rc].r-tr[rc].l+1),
    tr[lc].add+=tr[u].add,
    tr[rc].add+=tr[u].add,
    tr[u].add=0;      
  }
}
void build(LL u,LL l,LL r){ //建树
  tr[u]={l,r,w[l],0};
  if(l==r) return;
  LL m=l+r>>1;
  build(lc,l,m);
  build(rc,m+1,r);
  pushup(u);
}
void change(LL u,LL l,LL r,LL k){ //区修
  if(l<=tr[u].l&&tr[u].r<=r){
    tr[u].sum+=(tr[u].r-tr[u].l+1)*k;
    tr[u].add+=k;
    return;
  }
  LL m=tr[u].l+tr[u].r>>1;
  pushdown(u);
  if(l<=m) change(lc,l,r,k);
  if(r>m) change(rc,l,r,k);
  pushup(u);
}
LL query(LL u,LL l,LL r){ //区间查
  if(l<=tr[u].l && tr[u].r<=r) return tr[u].sum;
  LL m=tr[u].l+tr[u].r>>1;
  pushdown(u);
  LL sum=0;
  if(l<=m) sum+=query(lc,l,r);
  if(r>m) sum+=query(rc,l,r);
  return sum;
}
int main(){
  LL n,m,op,x,y,k;  
  cin>>n>>m;
  for(int i=1; i<=n; i ++) cin>>w[i];
  
  build(1,1,n);
  while(m--){
    cin>>op>>x>>y;
    if(op==2)cout<<query(1,x,y)<<endl;
    else cin>>k,change(1,x,y,k);
  }
  return 0;
}

CF786B Legacy

参考：

代码源自：「算法笔记」线段树优化建图 - maoyiting - 博客园

CF786B Legacy - 洛谷

原题：https://codeforces.com/contest/786/problem/B

现有一个图，有 n 个节点，从节点 s 出发，求到 n 个点每一个点的最短路。

其中，有三种建边方式 ：

• 建一条从 u 到 v 的单向边。
• 从节点 v 分别向 [l,r] 的每个结点连一条边。
• 从节点 [l,r] 向节点 v 连边。

思路：

对于操作二三，通过线段树把区间 [3,7] 拆成 [3,4]、[5,6] 和 [7,7] 然后分别连边。从O(n)到O(logn)

分别对操作二三建两棵树（用偏移量K实现）。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=3e6+5, K=5e5;  // N是最大节点数，K是线段树偏移量


int n, m, s;       // n-节点数, m-边数, s-源点
int opt, x, y, z, l, r, w;  // 操作类型和参数
int a[N];          // 存储每个原始节点对应的线段树节点
int cnt;           // 边计数器
int hd[N], to[N], nxt[N], val[N];  // 邻接表存储图
int d[N];          // 存储最短距离
bool v[N];         // 标记是否访问过
priority_queue<pair<int,int>> q;  // 优先队列用于Dijkstra

// 添加边函数
void add(int x, int y, int z) {
    to[++cnt] = y;         // 目标节点
    nxt[cnt] = hd[x];      // 下一条边
    hd[x] = cnt;           // 头指针
    val[cnt] = z;          // 边权值
}

// 构建线段树
void build(int p, int l, int r) {
    if(l == r) {           // 叶子节点
        a[l] = p;          // 存储原始节点对应的线段树节点
        return;
    }
    int mid = (l + r) / 2;
    // 添加父节点到子节点的边（权值为0）
    add(p, p<<1, 0);       // 左子节点
    add(p, p<<1|1, 0);     // 右子节点
    // 添加反向边（子节点到父节点）
    add((p<<1)+K, p+K, 0);    // 左子反向节点到父反向节点
    add((p<<1|1)+K, p+K, 0);  // 右子反向节点到父反向节点
    // 递归构建左右子树
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
}

// 修改操作（添加区间边）
void modify(int p, int l, int r, int lx, int rx, int v, int w) {
    if(l >= lx && r <= rx) {  // 当前区间完全包含在目标区间内
        if(opt == 2)          // 操作类型2：点v到区间[lx,rx]的边
            add(v+K, p, w);   // 从v的反向节点到当前线段树节点
        else                  // 操作类型3：区间[lx,rx]到点v的边
            add(p+K, v, w);   // 从当前线段树反向节点到v
        return;
    }
    int mid = (l + r) / 2;
    if(lx <= mid) modify(p<<1, l, mid, lx, rx, v, w);    // 处理左子树
    if(rx > mid) modify(p<<1|1, mid+1, r, lx, rx, v, w); // 处理右子树
}

// Dijkstra算法
void dij(int s) {
    memset(d, 0x3f, sizeof(d));  // 初始化距离为无穷大
    d[s] = 0;                    // 源点距离为0
    q.push(make_pair(0, s));      // 优先队列存储(距离,节点)
    
    while(q.size()) {
        int x = q.top().second;  // 取出当前距离最小的节点
        q.pop();
        
        if(v[x]) continue;       // 如果已经处理过则跳过
        v[x] = 1;                // 标记为已处理
        
        // 遍历所有邻接边
        for(int i = hd[x]; i; i = nxt[i]) {
            int y = to[i], z = val[i];
            if(d[y] > d[x] + z) {  // 松弛操作
                d[y] = d[x] + z;
                q.push(make_pair(-d[y], y));  // 使用负数实现最小堆
            }
        }
    }
}

signed main() {
    // 输入节点数、边数、源点
    scanf("%lld%lld%lld", &n, &m, &s);
    // 构建线段树
    build(1, 1, n);
    
    // 为每个原始节点添加双向边（原线段树节点和反向节点之间）
    for(int i = 1; i <= n; i++) {
        add(a[i], a[i]+K, 0);    // 原节点到反向节点
        add(a[i]+K, a[i], 0);    // 反向节点到原节点
    }
    
    // 处理每条边
    for(int i = 1; i <= m; i++) {
        scanf("%lld", &opt);     // 读取操作类型
        if(opt == 1) {           // 点对点边
            scanf("%lld%lld%lld", &x, &y, &z);
            add(a[x]+K, a[y], z); // 从x的反向节点到y的原节点
        } else {                  // 点对区间或区间对点边
            scanf("%lld%lld%lld%lld", &x, &l, &r, &w);
            modify(1, 1, n, l, r, a[x], w);  // 调用修改函数
        }
    }
    
    // 从源点的反向节点开始Dijkstra算法
    dij(a[s]+K);
    
    // 输出结果
    for(int i = 1; i <= n; i++) {
        // 如果距离不是无穷大则输出距离，否则输出-1
        printf("%lld%c", d[a[i]] != 0x3f3f3f3f3f3f3f3fll ? d[a[i]] : -1, 
              i == n ? '\n' : ' ');
    }
    
    return 0;
}

树状数组