线段树例题

HDU 1754

线段树板子题，结构体存保存的是左右端点以及这个区间内的最大值

建树的过程其实是一个后序遍历的过程，先建立左子树然后右子树，根节点的最大值就是 max(左孩子的最大值,右孩子的最大值)

修改类似，更新当前节点的最大值为 max(value, 当前节点的最大值)

查询的时候用一个全局变量记录，每次查找到对应区间，就更新全局变量 res = max(res, 当前区间的最大值)

Java会爆空间，只能用c做

#include <stdio.h>
#define Max 200001
struct data {
    int l, r, max;
}node[4 * Max];

int score[Max];
int res;
int max(int a, int b) {
    return a > b ? a : b;
}

void make(int l, int r, int idx) {
    node[idx].l = l;
    node[idx].r = r;
    if (l == r) 
        node[idx].max = score[l];
    else {
        make(l, (l + r) >> 1, (idx << 1) + 1);
        make(((l + r) >> 1) + 1, r, (idx << 1) + 2);
        node[idx].max = max(node[(idx << 1) + 1].max, node[(idx << 1) + 2].max);
    }
}

void update(int i, int value, int idx) {
    node[idx].max = max(value, node[idx].max);
    if (node[idx].l == node[idx].r)
        return;
    if (i <= (node[idx].l + node[idx].r) >> 1) // 左子树 
        update(i, value, (idx << 1) + 1);
    else // 右子树 
        update(i, value, (idx << 1) + 2);
}

void query(int l, int r, int idx) {
    if (l <= node[idx].l && r >= node[idx].r)
        res = max(res, node[idx].max);
    else {
        int mid = (node[idx].l + node[idx].r) >> 1;
        if (r <= mid)
            query(l, r, (idx << 1) + 1);
        else if (l > mid)
            query(l, r, (idx << 1) + 2);
        else {
            query(l, r, (idx << 1) + 1);
            query(l, r, (idx << 1) + 2);
        }
    }
}

int main() {
    int N,M;
    while(scanf("%d%d",&N,&M) != EOF) {
        for (int i = 1; i <= N; i++)
            scanf("%d",&score[i]);
        getchar();
        char c;
        int s,e;
        make(1,N,0);
        for (int i = 0; i < M; i++) {
            scanf("%c%d%d",&c,&s,&e);
            getchar();
            if (c == 'U')
                update(s,e,0);
            if (c == 'Q') {
                res = -1;
                query(s,e,0);
                printf("%d\n",res);
            }     
        }
    }
    return 0;
}

POJ 3468

题目大意是说给你一个数列A，有两种操作，一是将第a到b的数都加上c，二是询问a到b之间所有数的和

这是线段树的一种进阶应用——区间更新，区间查询

区间更新是指更新某个区间内的叶子节点的值，因为涉及到的叶子节点不止一个，而叶子节点会影响其非叶的父节点，那么回溯需要更新的非叶节点也会有很多，如果一次性更新完，操作的时间复杂度肯定不止O(logn)，例如当我们更新区间[1,7]内的值，就需要更新下图所示标红的所有节点

为此引入线段树的 延迟标记 概念，也叫 lazy tag

延迟标记：节点结构体中新增一个标记，记录这个节点是否会进行某种修改，对于任意区间的修改，我们先按照区间查询的方式将其划分成线段树中的节点，然后修改这些节点的信息，并给这些节点打上标记。在修改和查询的时候，如果我们到了一个节点P，并且要继续查看其子节点，那么我们就要看看节点P是否被标记，如果有，则需要按照其标记首先修改子节点的信息，并且给子节点都打上相同的标记，同时取消节点P的标记，这一操作称为 标记下放 ，也叫 pushDown

可以这么理解，假设爷爷要给两个孙女压岁钱，所以爷爷就先把总的压岁钱给自己的儿子，让儿子给女儿

，但是儿子觉得自己的女儿还太小了，暂时用不到，于是就先保存着。突然有一天爷爷准备要问孙女拿到压岁钱了没有，此时爸爸着急了，就赶紧把压岁钱给了女儿

具体在update函数中的操作就是，如果当前更新的区间为[l,r]，我走到节点P对应的区间是[curl,curr]，如果$[curl,curr] \in [l,r]$，那就先更新当前节点P，然后给P打上标记，P的子节点就不管了，直接return，如果以后进行查询或者更新操作的时候，发现当前节点有标记，才将标记下放

除了pushDown，还需要pushUp，pushDown的作用是将标记下放，而pushUp的作用是更新根节点的信息，因为子节点值改变了，根节点也会变，所以必须要更新根节点的信息

import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    static Node[] n;
    static long[] t;
    static long SUM;

    public static void main(String[] args) {
        Scanner cin = new Scanner(new InputStreamReader(System.in));
        int N = cin.nextInt();
        int M = cin.nextInt();
        n = new Node[4 * N];
        t = new long[N + 1];
        for (int i = 1; i <= N; i++)
            t[i] = cin.nextLong();
        make(1, N, 0);
        for (int i = 0; i < M; i++) {
            String op = cin.next();
            int a = cin.nextInt();
            int b = cin.nextInt();
            if ("Q".equals(op)) {
                SUM = 0;
                query(a, b, 0);
                System.out.println(SUM);
            } else { // "C".equals(op)
                int c = cin.nextInt();
                update(a, b, c, 0);
            }
        }
    }

    static void update(int l, int r, int c, int idx) {
        if (l <= n[idx].l && r >= n[idx].r) {
            n[idx].sum += (n[idx].r - n[idx].l + 1) * c;
            n[idx].inc += c;
            return;
        }
        if (n[idx].inc != 0)
            pushDown(idx);
        int mid = (n[idx].l + n[idx].r) >> 1;
        if (r <= mid)
            update(l, r, c, (idx << 1) | 1);
        else if (l > mid)
            update(l, r, c, (idx << 1) + 2);
        else {
            update(l, r, c, (idx << 1) | 1);
            update(l, r, c, (idx << 1) + 2);
        }
        pushUp(idx);
    }

    static void pushDown(int idx) {
        int mid = (n[idx].l + n[idx].r) >> 1;
        n[(idx << 1) | 1].sum += (mid - n[idx].l + 1) * n[idx].inc;
        n[(idx << 1) + 2].sum += (n[idx].r - mid) * n[idx].inc;
        n[(idx << 1) | 1].inc += n[idx].inc;
        n[(idx << 1) + 2].inc += n[idx].inc;
        n[idx].inc = 0;
    }

    static void query(int l, int r, int idx) {
        if (l <= n[idx].l && r >= n[idx].r)
            SUM += n[idx].sum;
        else {
            if (n[idx].inc != 0)
                pushDown(idx);
            int mid = (n[idx].l + n[idx].r) >> 1;
            if (r <= mid)
                query(l, r, (idx << 1) | 1);
            else if (l > mid)
                query(l, r, (idx << 1) + 2);
            else {
                query(l, r, (idx << 1) | 1);
                query(l, r, (idx << 1) + 2);
            }
        }
    }

    static void make(int l, int r, int idx) {
        n[idx] = new Node();
        n[idx].l = l;
        n[idx].r = r;
        if (l == r)
            n[idx].sum = t[r];
        else {
            make(l, (l + r) >> 1, (idx << 1) | 1); // 左子树
            make(((l + r) >> 1) + 1, r, (idx << 1) + 2); // 右子树
            pushUp(idx);
        }
    }

    static void pushUp(int idx) {
        n[idx].sum = n[(idx << 1) | 1].sum + n[(idx << 1) + 2].sum;
    }
}

class Node {
    int l, r;
    long sum;
    long inc;
}

类似的线段树区间更新题目还有 CDOJ 秋实大哥与花

POJ 2528

题目大意，有一面墙，被等分成1千万份。现在往墙上贴N张海报，每张海报的宽度是任意的（必定是整数，且小于1千万）。后贴的海报若与先贴的海报有交集，后贴的海报就会全部或局部覆盖先贴的海报，现在给出每张海报所贴的位置（左端点和右端点），问贴完N张海报后，还能看见多少张海报（看见一部分也算看到）

这是一道区间压缩映射（离散化）线段树问题，首先抽象问题：给定一条数轴，长度为1千万，然后在数轴上的某些区间贴海报，第i次对区间贴的海报为i，给出每次贴海报的区间，问最后能看见都少张海报

这道题单纯用线段树去求解需要建立一棵[1,1千万]的线段树，MLE是铁定的，所以必须 离散化

通俗点说，离散化就是压缩区间，使原有的长区间映射到新的短区间，但是区间压缩前后的覆盖关系不变。举个例子：

有一条1到10的数轴，长度为9，给定4个区间[2,4] [3,6] [8,10] [6,9]，后者覆盖前者，每个区间编号依次为1 2 3 4

现在我们抽取这4个区间的8个端点 2 4 3 6 8 10 6 9，删除重复的端点，对其升序 排序 得2 3 4 6 8 9 10，然后建立映射

那么新的4个区间为[1,3] [2,4] [5,7] [4,6]，覆盖关系也没有改变，新数轴为1到7

这就完了吗，这样做真的对吗？考虑一组数据，假如三张海报的区间为[1,10] [1,4] [6,10]，离散化后x[1]=1,x[2]=4,x[3]=6,x[4]=10

放第一张海报时：墙的1-4标记为1

放第二张海报时：墙的1-2被标记为2，3-4仍为1

放第三张海报时：墙的3-4被标记为3，1-2仍为2

最终，第一张海报就被完全覆盖了，于是输出2，但实际上正确输出应该为3

争取的离散方法是：在相差大于1的数间加一个数，例如在上面1 4 6 10中间加5

x[1]=1,x[2]=4,x[3]=5,x[4]=6,x[5]=10

这样之后，第一次是1-5变成1，第二次1-2变成2，第三次4-5变成3

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int n;
struct CPost { // 海报
    int l,r;
} posters[10100];
int x[20200]; // 海报的端点瓷砖编号
int hashArr[10000010]; // hashArr[i]表示瓷砖i所处的离散化后区间编号

struct CNode {
    int l,r;
    bool bCovered; // 区间[l,r]是否被完全覆盖
    CNode *pLeft, *pRight; 
} Tree[1000000];
int nNodeCount = 0; // 记录线段树结点数 
int mid(CNode *pRoot) {
    return (pRoot->l + pRoot->r) >> 1;
} 
void buildTree(CNode *pRoot, int l, int r) {
    pRoot->l = l;
    pRoot->r = r;
    pRoot->bCovered = false;
    if (l == r)
        return;
    nNodeCount++;
    pRoot->pLeft = Tree + nNodeCount;
    nNodeCount++;
    pRoot->pRight = Tree + nNodeCount;
    buildTree(pRoot->pLeft, l, (l + r) >> 1);
    buildTree(pRoot->pRight, ((l +r) >> 1) + 1, r);
}
bool post(CNode *pRoot, int l, int r) {
    if (pRoot->bCovered)
        return false;
    if (pRoot->l == l && pRoot->r == r) {
        pRoot->bCovered = true;
        return true;
    }
    bool result;
    if (r <= mid(pRoot))
        result = post(pRoot->pLeft, l, r);
    else if (l > mid(pRoot))
        result = post(pRoot->pRight, l, r);
    else {
        bool b1 = post(pRoot->pLeft, l, mid(pRoot));
        bool b2 = post(pRoot->pRight, mid(pRoot) + 1, r);
        result = b1 || b2;
    }
    if (pRoot->pLeft->bCovered && pRoot->pRight->bCovered)
        pRoot->bCovered = true;
    return result;
}

int main() {
    int t,i,j,k;
    scanf("%d",&t);
    int nCaseNo = 0;
    while (t--) {
        nCaseNo++;
        scanf("%d",&n);
        int nCount = 0; // 记录海报端点数 
        for (i = 0; i < n; i++) {
            scanf("%d%d", &posters[i].l, &posters[i].r);
            x[nCount++] = posters[i].l;
            x[nCount++] = posters[i].r;
        }
        sort(x, x + nCount);
        nCount = unique(x, x + nCount) - x; // 去重
        // 离散化
        int nlntervalNo = 0;
        for (i = 0; i < nCount; i++) {
            hashArr[x[i]] = nlntervalNo;
            if (i < nCount - 1) {
                if (x[i + 1] - x[i] == 1)
                    nlntervalNo++;
                else
                    nlntervalNo += 2;
            }
        } 
        buildTree(Tree, 0, nlntervalNo);
        int nSum = 0;
        for (i = n - 1; i >= 0; i--) {
            if (post(Tree, hashArr[posters[i].l], hashArr[posters[i].r]))
                nSum++;
        }
        printf("%d\n",nSum);
    }
    return 0;
}