线段树·登场

树状数组擅长“和”这类可加信息，但区间最大值、区间赋值等它就难办。线段树把区间递归二分，每个节点存一段区间的信息，能处理更广的区间问题，修改和查询都是 O(log n)。