【算法】线段树

线段树

线段树的根节点是整段区间，其它结点是由区间不断二分得到的子区间，其中叶子结点是区间的每个单独的元素。

存储

这里使用结构体存线段树。

struct Tree {
    int left, right;
    long long value, lazy;//结点维护的值及懒标记
}tree[4*maxn+2];//注意数组大小至少要开到区间长度的四倍大

建树

这里默认我们要求的是区间和，故结点值均为区间和。

可以视情况改变结点值的含义。

void build(int left, int right, int index) {
  //编号为index的结点维护的区间所对应的原数组下标为left到right
    tree[index].left = left;
    tree[index].right = right;
    if (left == right) {//到达叶子结点
        tree[index].value = a[l];
        return;
    }
    int mid = (right + left) / 2;
    build(left, mid, index * 2);
    build(mid + 1, right, index * 2 + 1);
    tree[index].value = tree[index * 2].value + tree[index * 2 + 1].value;
    //不是叶子结点，则其值为左子树加右子树
}

懒标记

如果每次对叶子结点的值进行修改时，总是一并将受其影响的其他父结点的值一起修改，耗时会比较长。

于是我们在接到修改命令之后，可以先将受到影响的最上层结点打上lazy标记，存储要修改的值。等到查询的时候，执行先前被延迟的修改操作，再将懒标记下放，从而达到向下层层修改的效果。如此一来可以节省很多时间。

void spread(int i) {
    if (tree[i].lazy) {//如果该结点有懒标记
        int lc = i * 2, rc = i * 2 + 1;//左右子结点的下标
        //括号里算的是子结点的区间长度，乘以lazy就是将相关叶子结点加上lazy之后的新的和
        tree[lc].value += tree[i].lazy * (tree[lc].right - tree[lc].left + 1);
        tree[rc].value += tree[i].lazy * (tree[rc].right - tree[rc].left + 1);
        //为结点的左右结点打上标记
        tree[lc].lazy += tree[i].lazy;
        tree[rc].lazy += tree[i].lazy;
        //标记下传之后将该结点的懒标记清零
        tree[i].lazy = 0;
    }
}

区间修改

void change(int i, int x, int y, int z) {
    //要给区间[x,y]加上一个数z，先从根结点i向下找相应的结点
    if (x <= tree[i].left && y >= tree[i].right) {
        //如果[x,y]完全覆盖到了该结点表示的区间，就执行更新
        tree[i].value += z * (tree[i].right - tree[i].left + 1);
        //暂时只更新这个结点的值
        tree[i].lazy += z;
        //打上懒标记，表示其子结点的值仍待更新
        return;
        //直接返回上一层
    }
  else{ //如果[x,y]没有完全覆盖该结点表示的区间，则继续向下找
    spread(i);
    //考虑到该结点可能有需要下放的懒标记，先将懒标记下放
    int mid = (tree[i].left + tree[i].right) / 2;
    if (x <= mid) change(i * 2, x, y, z);
    //如果[x,y]覆盖到了左子结点，更新
    if (y > mid) change(i * 2 + 1, x, y, z);
    //如果[x,y]覆盖到了右子结点，更新
    tree[i].value = tree[i * 2].value + tree[i * 2 + 1].value;
    //最后更新该结点的值
    }
}

区间查询

int ask(int i, int x, int y) {
    //询问区间[x,y]的和，先从根节点i向下找
    if (x <= tree[i].left && y >= tree[i].right) return tree[i].value;
    ////如果[x,y]完全覆盖到了该结点表示的区间，返回这个结点的值（即结点表示的区间的和）
    else {
        int ans = 0;
        spread(i);
        //下放懒标记
        int mid = (tree[i].left + tree[i].right) / 2;
        if (x <= mid) ans += ask(i * 2, x, y);
        if (y > mid) ans += ask(i * 2 + 1, x, y);
        return ans;
    }
}