概念引入 线段树是一种二叉树,也就是说,每个线段都可以用一二叉树表示 比如一个长度为4的线段可以如此表示: ——————————————-4 1————-2————-3————4 1 2 3 4 如果你要表示线段上的和,最上面的根表示线段1~4的和 下面两个子节点表示1 ~ 2,3 ~ 4的和,以此类推...... ☽:sun:☽:sun:卐 然后我们还可以得到一个性质:节点i的权值=她的左儿子权值+她的右儿子权值。 根据这个思路,我们就可以建树了:设一个结构体tree[i]; tree[i].sum表示当前的线段