线段树

什么是线段树

线段树，相似区间树，是一个齐全二叉树，它在各个节点保留一条线段（数组中的一段子数组），次要用于高效解决间断区间的动静查问问题，因为二叉构造的个性，它根本能放弃每个操作的复杂度为O(logn)

经典线段树问题：区间染色

有一面墙，长度为n，每次抉择一段墙进行染色

m次操作后，咱们能够看见几种色彩？

m次操作后，咱们能够在[i,j]区间看见多少种颜色？

线段树的根本示意

public class SegmentTree<E> {        private E[] data;        private E[] tree;        public SegmentTree(E[] arr) {            data = (E[]) new Object[arr.length];            for (int i = 0; i < arr.length; i++) {                data[i] = arr[i];            }            tree = (E[]) new Object[4 * arr.length];        }        public E get(int index) {            if (index < 0 || index >= data.length) {                throw new IllegalArgumentException("Index is illegal.");            }            return data[index];        }        public int getSize() {            return data.length;        }        // 返回齐全二叉树的数组示意中，一个索引所示意的元素的左孩子节点的索引        private int leftChild(int index){            return 2 * index + 1;        }        // 返回齐全二叉树的数组示意中，一个索引所示意的元素的右孩子节点的索引        private int rightChild(int index){            return 2 * index + 2;        }    }

如何在线段树中查问2，5

首先咱们先失去根节点，咱们会发现2在0……3区间中，而5在4……7区间中。

这样的话咱们能够拿到根节点的两个子节点。

0……3的左孩子不蕴含2……3节点所以咱们去获取右孩子节点即可，4……7同理。

之后咱们将两个节点组合起来即可。

创立线段树及查问

public interface Merger<E> {    E merge(E a,E b);}

public class SegmentTree<E> {        private E[] data;        private E[] tree;        private Merger<E> merger;        public SegmentTree(E[] arr, Merger<E> merger) {            data = (E[]) new Object[arr.length];            for (int i = 0; i < arr.length; i++) {                data[i] = arr[i];            }            tree = (E[]) new Object[4 * arr.length];            buildSegmentTree(0, 0, data.length - 1);            this.merger = merger;        }        //在treeIndex的地位创立示意区间【l...r】的线段树        private void buildSegmentTree(int treeIndex, int l, int r) {            if (l == r) {                tree[treeIndex] = data[l];                return;            }            int leftTreeIndex = leftChild(treeIndex);            int rightTreeIndex = rightChild(treeIndex);            int mid = l + (r - l) / 2;            buildSegmentTree(leftTreeIndex, l, mid);            buildSegmentTree(rightTreeIndex, mid + 1, r);            tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);        }        public E get(int index) {            if (index < 0 || index >= data.length) {                throw new IllegalArgumentException("Index is illegal.");            }            return data[index];        }        public int getSize() {            return data.length;        }        // 返回齐全二叉树的数组示意中，一个索引所示意的元素的左孩子节点的索引        private int leftChild(int index) {            return 2 * index + 1;        }        // 返回齐全二叉树的数组示意中，一个索引所示意的元素的右孩子节点的索引        private int rightChild(int index) {            return 2 * index + 2;        }        //返回区间值[queryL,queryR]        public E query(int queryL, int queryR) {            if (queryL < 0 || queryR >= data.length || queryR < 0 || queryR >= data.length || queryL > queryR) {                throw new IllegalArgumentException("Index is illegal.");            }            return query(0, 0, data.length - 1, queryL, queryR);        }        //在以treeID为根的线段树中【l...r】的范畴里，搜寻区间【queryL...queryR】的值        private E query(int treeIndex, int l, int r, int queryL, int queryR) {            if (l == queryL && r == queryR) {                return tree[treeIndex];            }            int mid = l + (r - l) / 2;            int leftTreeIndex = leftChild(treeIndex);            int rightTreeIndex = rightChild(treeIndex);            if (queryL >= mid + 1) {                return query(rightTreeIndex, mid + 1, r, queryL, queryR);            } else if (queryR <= mid) {                return query(leftTreeIndex, l, mid, queryL, queryR);            }            E leftResult = query(leftTreeIndex, l, mid, queryL, mid);            E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);            return merger.merge(leftResult, rightResult);        }        //将index地位的值，更新为e        public void set(int index, E e) {            if (index < 0 || index >= data.length) {                throw new IllegalArgumentException("Index is illegal.");            }            data[index] = e;            set(0, 0, data.length - 1, index, e);        }        // 在以treeIndex为根的线段树中更新index的值为e        private void set(int treeIndex, int l, int r, int index, E e) {            if (l == r) {                tree[treeIndex] = e;                return;            }            int mid = l + (r - l) / 2;            int leftTreeIndex = leftChild(treeIndex);            int rightTreeIndex = rightChild(treeIndex);            if (index >= mid + 1) {                set(rightTreeIndex, mid + 1, r, index, e);            } else {                set(leftTreeIndex, l, mid, index, e);            }            tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);        }}