TYS的博客

算法小白努力学习中

0%

线段树

发表于 更新于 分类于

每个叶子节点为最小的分割区间，即为数组存储的值。

假设树的高度为k，0,1,2$\dots$k，另n为区间个数，则有$2^{k - 1} < n \le 2^k$，整棵树的节点个数有$2^{k + 1} - 1$个，通常线段树空间大小为4 * n

leetcode 1109 航班预订统计

leetcode 307 区间和检索-数组可修改

leetcode 308 二维区域和检索—可变

线段树建树

数组下标同树状数组相同，都是从1开始

1
2
3
4
5
6
7
8
9
10
void build(int l, int r, int p) {
    if(l == r) {
        d[p] = a[l];
        return;
    }
    int mid = l + (r - l) / 2;
    build(l, m, p << 1);
    build(m + 1, r, p << 1 | 1);
    d[p] = d[p << 1] + d[p << 1 | 1];
}

线段树区间查询

l，r为查询区间，cl，cr为当前区间的左右边界。

1
2
3
4
5
6
7
8
9
int query(int l, int r, int p, int cl, int cr) {
    if(cl > r || cr < l) return 0;
    else if(l <= cl && r >= cr) return d[p];
    else {
        int mid = l + (r - l) / 2, sum = 0;
        if(l <= mid) sum += query(l, r, p << 1, cl, mid);
        if(r > mid) sum += quert(l, r, p << 1 | 1s, mid + 1, cr);
    }
}

线段树的点更新$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
void update(int k, int v, int l, int r, int p) {  //update(k, v, 1, n, 1)
    if(l == r) a[k] += v, d[k] += v;
    else {
        int mid = l + (r - l) / 2;
        if(k <= mid) {
            update(k, v, l, mid, p << 1);
        } else {
            update(k, v, mid + 1, r, p << 1 | 1);
        }
        d[p] = d[p << 1] + d[p << 1 | 1];
    }
}

线段树区间修改与懒惰标记

对于一个区间$[l, r]$，如果每次更新区间中的每个值，那么时间复杂度为$O(nlogn)$，为了提高更新效率，采用了mark进行标记。在递归更新过程中，当当前节点区间为待更新区间的真子集时，不再向下更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void push_down(int p, int len) {
    mark[p << 1] += mark[p];
    mark[p << 1 | 1] += mark[p];
    d[p << 1] += mark[p] * (len - len / 2);
    d[p << 1 | 1] += mark[p] * len / 2;
    mark[p] = 0;
}

void update(int l, int r, int val, int cl, int cr, int p) {
    if(l > cr || r < cl) return;
    else if(l <= cl && r >= cr) {
        d[p] += (cr - cl + 1) * val;
        if(cl > cr) mark[p] += d;
    } else {
    	int mid = cl + (cr - cl) / 2;
        push_down(p, cr - cl + 1);
        update(l, r, val, cl, mid, p << 1);
        update(l, r, val, mid + 1, cr, p << 1 | 1);
        d[p] = d[p << 1] + d[p << 1 | 1];
    }
}

线段树区间查询 包含懒惰标记

1
2
3
4
5
6
7
8
9
int query(int l, int r, int cl, int cr, int p) {
    if(l > cr || r < cl) return 0;
    else if(l <= cl && r >= cr) return d[p];
    else {
        int mid = l + (r - l) / 2;
	    if(mark[p]) push_down(p, cr - cl + 1);
        return query(l, r, cl, mid, p << 1) + query(l, r, mid + 1, cr, p << 1 | 1);
    }
}