Note: This article is available in Chinese only. 本文暂无英文版本。
View original
嘛，终于下定决心搞定线段树了。
之前几次都是被lazy标记卡住，这次大概不会了吧2333
放一些学习资料，最后比较zkw线段树和普通线段树的区别。
codeforces上非递归线段树讲解 （其实就是zkw吧）
找到了一篇非常赞的tutorial（含lazy标记） 链接
线段树学习笔记
Related
hdoj 2795 Billboard
http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意：一个尺寸为wh的方格。要按顺序放放n个尺寸为1wi的纸条。问每一个纸条回被放在哪里。如果有多个，放在最上面（编号小） 思路：把没横行能放的最大长度看做一个序列建树。由于h比n大很多。。多出来的没用。。直接取较小值就行。
hdu 1754 I Hate It (线段树)
I Hate It # **Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 53991 Accepted Submission(s): 21180 **
Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。
hdu 3333 Turing Tree (求区间中不相同数的和，离线+线段树/树状数组)
题目链接
喵呜，离散树状数组。
这道题由于相同的值加和的时候只算一次，所以比较伤脑筋==
怎么办呢？
我们发现对于一个值，由于相同的只算一次，所以在任意时间内，这个值只需要出现一次。
poj 2481 Cows(树状数组||线段树)
poj 2481 题目链接
题意：给定n个区间，问对于每个区间，有多少个区间真包含该区间（真包含的意思是说，两个区间不能完全重合）
思路：
下面是一年前用树状数组过掉的时候写的题解： 和 star那道题差不多。
poj 2352 Stars （树状数组||线段树）
poj 2352题目链接
题意：给出n个星星的位置，一个星星的level定义为其左下角（不严格）星星的数量。
要求统计0到n-1 level的星星各有多少个。
下面是一年前写的树状数组的题解：