线段树

线段树是一种基于分治思想的二叉树结构,用于在区间上进行信息统计,区间修改.

线段树有如下几种性质

1·每个节点代表一个区间

2·唯一的根节点,代表全部区间

3·每个叶子节点代表一个长度为1的区间

对于每个内部节点 非叶节点,左子节点[l,mid] 右子节点[mid + 1,r]

存储方式

使用数组,仿照二叉堆存储,父的左孩子是 x * 2,右孩子是 x * 2 + 1

使用struct结构存储最后一层会产生空余, 所以数组长度必须为 4N,才不会越界

建树

struct SegmentTree{
    int sum,mul,add,maxm;
}tree[MAX_N << 2];
 void build(int root, int l, int r){
     tree[root].mul = 1;
     tree[root].add = 0;
     if(l == r)tree[root].sum = a[l];
     else{
         int mid = (l + r) >> 1;
         build(root * 2, l, mid + 1);
         build(root << 1 | 1, mid + 1,r);
      //求区间最大   tree[root].sum = max(tree[root << 1].sum ,tree[root * 2 + 1].sum);
      //求区间和值   tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
      //主要是给每个区间的的父节点存储信息,这棵树想要存储什么信息,那就在此记录什么信息,从下至上
     }
 }

单点修改

递归找到[x,x]的叶节点 然后从下至上更新,所有祖先节点保存的信息

void change(int root,int l ,int r, int x,int v) // 将[x,x]区间值改为 v
{
    if(l == r && l == x && r == x){
        tree[root].val = v;
        return ;
    }
    else {
        int mid = (l + r) >> 1;
        if(x <= mid)
        change(root * 2 ,l,mid,x,v);
        else
        change(root * 2 ,mid + 1,r,x,v);
       //自下向上传递我们想要维护的信息,比如我们想要维护最大值,则在此区间选取左右孩子的最大值传递
       //tree[root].val = max(leftchild_maxval,rightchild,maxval); 
    }   
}

区间查询

区间查询从根节点开始,递归向下查询:

1·若[l,r]完全覆盖当前节点代表的区间,则立即回溯,并且该节点的val值为当前区间的最大值

2·若左子节点与[l,r]有重叠部分,则递归访问左子节点

3·若右子节点与[l,r]有重叠部分,则递归访问右子节点

long long query(int root, int l,int r,int lind, int rind){ //l r查询区间,lind和rind为总
    if(l <= lind && r >= rind){
        return tree[root].sum;
    }
    if(r < lind || l > rind){
        return 0;
    }
    DOWN(root,lind,rind);
    int mid = (lind + rind) >> 1;
    return query(root * 2,l,r,lind,mid) + query(root * 2 + 1,l,r,mid + 1,rind);
}

线段树维护最大连续子段和

处理区间端点外,再维护4个信息,区间和,区间最大连续子段和,紧靠左端的最大连续子段和,紧靠右端的最大连续子段和(sum, dat,lmax, rmax)`

线段树:最大公约数(GCD)区间GCD问题

根据gcd(x,y,z) = gcd(x,y - x,z - y) 转换为求差分后的gcd

线段树求矩形并面积