线段树与树状数组 | 谷歌脸书都爱考，求职者最怕考

在各类算法题中，线段树是一个强大而十分好用的数据结构，能很好地解决动态接受单点修改而同时快速返回区间信息的需求，并且降低你的思维复杂度和 coding 的复杂度。谷歌脸书都爱考线段树本来是信息学竞赛的常客，但近几年，算法面试也出现了它的身影，很多求职者都跪在了线段树。比如，谷歌就比较喜欢考，有时第一题就上线段树，有同学在脸书电面就碰上了线段树。 一道题能不能用线段树来做，基本是看这道题的操作有没有区间的性质。也就是在一个区间上的操作是否可以转化为两个子区间上的操作。几种常见的线段树套路1. 求区间的和，积，最大值，最match小值，gcd等2. 以当前结点的值作为结点处理，比如给出N个数，再给一个数，问比这个数大的有多 ………………………………