Leetcode刷题笔记
DP模块
1.最长回文字符串：
解决策略：基于回文字符串的长度，从短到长动态规划，然后给出对应的状态转移方程降低时间复杂度，注意状态转移的边界
基于这个思路给出基本的状态转移方程：
对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”。
写完状态转移方程之后，注意框定边界，<3的长度的字符串，就需要特判解决，并且注意状态转移应该是从短到长的。
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
boolean[][] dp = new boolean[len][len];
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= len; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < len; i++) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= len) {
break;
}
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}2.正则表达式匹配
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.'Matches any single character.'*'Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Example 1:Input: s = “aa”, p = “a” Output: false Explanation: “a” does not match the entire string “aa”.
Example 2:Input: s = “aa”, p = “a*” Output: true Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.
Example 3:Input: s = “ab”, p = “.*” Output: true Explanation: “.*” means “zero or more (*) of any character (.)”.
Constraints:
1 <= s.length <= 201 <= p.length <= 20scontains only lowercase English letters.pcontains only lowercase English letters,'.', and'*'.- It is guaranteed for each appearance of the character
'*', there will be a previous valid character to match.
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public boolean isMatch(String s, String p) {
// dp[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
// 初始化
dp[0][0] = true;
// 初始化 s 为空时的情况
for (int j = 1; j <= p.length(); j++) {
// p 的第 j 个字符为 * 时，可以将 p 的前 j - 2 个字符删除
// 因此 dp[0][j] = dp[0][j - 2]
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
} else { // p 的第 j 个字符不为 * 时，无法匹配
dp[0][j] = false;
}
}
// 初始化 p 为空时的情况
for (int i = 1; i <= s.length(); i++) {
dp[i][0] = false;
}
// 递推
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
// s 的第 i 个字符与 p 的第 j 个字符相等时，dp[i][j] = dp[i - 1][j - 1]
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
// s 的第 i 个字符与 p 的第 j 个字符相等时，dp[i][j] = dp[i - 1][j - 1]
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') { // p 的第 j 个字符为 * 时
// s 的第 i 个字符与 p 的第 j - 1 个字符相等时，dp[i][j] = dp[i - 1][j]
if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
// s 的第 i 个字符与 p 的第 j - 1 个字符相等时，dp[i][j] = dp[i - 1][j]
dp[i][j] = dp[i - 1][j];
}
// s 的第 i 个字符与 p 的第 j - 2 个字符相等时，dp[i][j] = dp[i][j - 2]
// 因为 * 可以匹配 0 个前面的字符
// s 的第 i 个字符与 p 的第 j - 2 个字符不相等时，dp[i][j] = dp[i][j - 2]
// 因为 * 可以匹配 0 个前面的字符
dp[i][j] = dp[i][j] || dp[i][j - 2];
} else { // s 的第 i 个字符与 p 的第 j 个字符不相等时，无法匹配
dp[i][j] = false;
}
}
}
return dp[s.length()][p.length()];
}
}
//leetcode submit region end(Prohibit modification and deletion)
解题思路：
从左往右扫的话
- 字符后面是否跟着星号会影响结果，分析起来有点复杂。
选择从右往左扫描
- 星号的前面肯定有一个字符，星号也只影响这一个字符，它就像一个拷贝器。
- s、p 串是否匹配，取决于：最右端是否匹配、剩余的子串是否匹配。
- 只是最右端可能是特殊符号，需要分情况讨论而已。
通用地表示出子问题
- 大子串是否匹配，和剩余子串是否匹配，是规模不一样的同一问题。
情况1：s[i−1] 和 p[j−1] 是匹配的
- 最右端的字符是匹配的，那么，大问题的答案 = 剩余子串是否匹配。
情况2：s[i−1] 和 p[j−1] 是不匹配的
- 右端不匹配，还不能判死刑——可能是 p[j−1] 为星号造成的不匹配，星号不是真实字符，它不匹配不算数。
- 如果 p[j−1] 不是星号，那就真的不匹配了。
p[j−1]==”∗”，且 s[i−1] 和 p[j−2] 匹配
- p[j−1] 是星号，并且 s[i−1] 和 p[j−2] 匹配，要考虑三种情况：
- p[j−1] 星号可以让 p[j−2] 在 p 串中消失、出现 1 次、出现 >=2 次。
- 只要其中一种使得剩余子串能匹配，那就能匹配，见下图 a1、a2、a3。
- a3 情况：假设 s 的右端是一个 a，p 的右端是 a * ，* 让 a 重复 >= 2 次
- 星号不是真实字符，s、p是否匹配，要看 s 去掉末尾的 a，p 去掉末尾一个 a，剩下的是否匹配。
- 星号拷贝了 >=2 个 a，拿掉一个，剩下 >=1 个a，p 末端依旧是 a* 没变。
- s 末尾的 a 被抵消了，继续考察 s(0,i-2) 和 p(0,i-1) 是否匹配。
p[j−1]==”∗”，但 s[i−1] 和 p[j−2] 不匹配
- s[i−1] 和 p[j−2] 不匹配，还有救，p[j−1] 星号可以干掉 p[j−2]，继续考察 s(0,i−1) 和 p(0,j−3)。
base case
p为空串，s不为空串，肯定不匹配。s为空串，但p不为空串，要想匹配，只可能是右端是星号，它干掉一个字符后，把p变为空串。s、p都为空串，肯定匹配。
3.编辑步数
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Example 1:Input: word1 = “horse”, word2 = “ros” Output: 3 Explanation: horse -> rorse (replace ‘h’ with ‘r’) rorse -> rose (remove ‘r’) rose -> ros (remove ‘e’)
Example 2:Input: word1 = “intention”, word2 = “execution” Output: 5 Explanation: intention -> inention (remove ‘t’) inention -> enention (replace ‘i’ with ‘e’) enention -> exention (replace ‘n’ with ‘x’) exention -> exection (replace ‘n’ with ‘c’) exection -> execution (insert ‘u’)
Constraints:
0 <= word1.length, word2.length <= 500word1andword2consist of lowercase English letters.
此题解拷贝自leetcode
思路过程可以如下：
需要求解的是word1编辑到word2所需要的步骤最小值，是不是可以先把word1的一个子串编辑成word2的一个子串？然后随着子串的长度逐渐变大，是否可以推导出结果？
用W1Si表示word1的子串（sub(0, i))，W2Sj表示word2的子串（sub(0, j))；
二维数组dp[i][j] 代表把 W1Si编辑成 W2Sj所需要的最少步数；
假如现在word1为horse，word2为ros；
把horse转化为ros，可以转换思路，可在已知以下三种情况之下，再做一个额外的操作，实现把horse编辑为ros:
1、当前已经有hors编辑为ros的步骤，那么可以在原word1（horse）基础之上，删除最后的e，也可以得到ros；
2、当前已经有horse编辑成ro的步骤，那么可以在原word1（horse）基础之上，插入一个s，也可以得到ros；
3、当前已经有了hors编辑成ro的步骤，那么可以在原word1（horse）基础之上，把最后的一个e替换成s，也可以得到ros;
特殊情况下：
hors->ros，其实就等于hor->ro;
#状态转移方程
那么就可以认为上面三种情况下最小值，就是最终结果：
dp(horse->ros) = min{dp(hors->ros), dp(horse->ro), dp(hors->ro)} + 1;
即：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
特殊情况下：
如果word1[i]==word2[j]，那么dp[i][j]=dp[i-1][j-1];
#边界
现在来看边界：
边界是i=0或者j=0；
如果i=0，表示从horse的一个空子串（“”）编辑成ros的所有子串（””、“r”、“ro”、“ros”）所需要的步数，每一个都执行插入就可以了，结果为dp[0][j] = j；
如果j=0，表示从horse的所有子串（“”、“h”、“ho”、“hor”、”hors”、“horse”）编辑成ros的一个空子串（“”）所需要的步数，每一步都执行删除就可以了，结果为dp[i][0]=i；
class Solution {
public int minDistance(String word1, String word2) {
int size1 = word1.length();
int size2 = word2.length();
//子串都应包含空串，所以长度都+1
int[][] dp = new int[size1 + 1][size2 + 1];
for (int i = 0; i <= size1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= size2; j++) {
dp[0][j] = j;
}
//都从不为空串的第一个子串开始
for (int i = 1; i <= size1; i++) {
for (int j = 1; j <=size2; j++) {
if (word1.charAt(i-1) == word2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j]) + 1;
}
}
}
return dp[size1][size2];
}
}3.maximum Matrix
有一个很慢的但是很舒服的方法，用二维前缀和去处理对应的长方形存在性，代码在下面贴出来
public int maximalRectangle(char[][] matrix) {
int[][] dp = new int[matrix.length+5][matrix[0].length+5];
dp[0][1]=dp[1][0]=dp[0][0]=0;
dp[1][1]=matrix[0][0]=='1'?1:0;
for(int i = 1;i <= matrix.length;i++){
for(int j = 1;j <= matrix[0].length;j++){
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+(matrix[i-1][j-1]=='1'?1:0);
}
}
for(int i = 0;i <= matrix.length;i++){
for(int j = 0;j <= matrix[0].length;j++){
System.out.print(dp[i][j]+" ");
}
System.out.println();
}
int max = 0;
for(int i = 1;i <= matrix.length;i++){
for(int j = 1;j <= matrix[0].length;j++){
if(matrix[i-1][j-1]=='0') continue;
for(int k = matrix.length;k >=i ;k--){
for(int l = matrix[0].length;l >= j;l--){
if(dp[k][l]-dp[i-1][l]-dp[k][j-1]+dp[i-1][j-1]==(k-i+1)*(l-j+1)){
max = Math.max(max,(k-i+1)*(l-j+1));
break;
}
}
}
}
}
return max;
}但还有一个更加tricky的办法
We can apply the maximum in histogram in each row of the 2D matrix. What we need is to maintain an int array for each row, which represent for the height of the histogram.
Please refer to https://leetcode.com/problems/largest-rectangle-in-histogram/ first.
Suppose there is a 2D matrix like
1 1 0 1 0 1
0 1 0 0 1 1
1 1 1 1 0 1
1 1 1 1 0 1
First initiate the height array as 1 1 0 1 0 1, which is just a copy of the first row. Then we can easily calculate the max area is 2.
Then update the array. We scan the second row, when the matrix[1][i] is 0, set the height[i] to 0; else height[i] += 1, which means the height has increased by 1. So the height array again becomes 0 2 0 0 1 2. The max area now is also 2.
Apply the same method until we scan the whole matrix. the last height arrays is 2 4 2 2 0 4, so the max area has been found as 2 * 4 = 8.
Then reason we scan the whole matrix is that the maximum value may appear in any row of the height.
Code as follows:
public class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int[] height = new int[matrix[0].length];
for(int i = 0; i < matrix[0].length; i ++){
if(matrix[0][i] == '1') height[i] = 1;
}
int result = largestInLine(height);
for(int i = 1; i < matrix.length; i ++){
resetHeight(matrix, height, i);
result = Math.max(result, largestInLine(height));
}
return result;
}
private void resetHeight(char[][] matrix, int[] height, int idx){
for(int i = 0; i < matrix[0].length; i ++){
if(matrix[idx][i] == '1') height[i] += 1;
else height[i] = 0;
}
}
public int largestInLine(int[] height) {
if(height == null || height.length == 0) return 0;
int len = height.length;
Stack<Integer> s = new Stack<Integer>();
int maxArea = 0;
for(int i = 0; i <= len; i++){
int h = (i == len ? 0 : height[i]);
if(s.isEmpty() || h >= height[s.peek()]){
s.push(i);
}else{
int tp = s.pop();
maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
i--;
}
}
return maxArea;
}
}4.大礼包
在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。
还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。
返回 确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。
示例 1：
输入：price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
输出：14
解释：有 A 和 B 两种物品，价格分别为 ¥2 和 ¥5 。 大礼包 1 ，你可以以 ¥5 的价格购买 3A 和 0B 。 大礼包 2 ，你可以以 ¥10 的价格购买 1A 和 2B 。 需要购买 3 个 A 和 2 个 B ， 所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A 。
首先，我们过滤掉不需要计算的大礼包。
如果大礼包完全没有优惠（大礼包的价格大于等于原价购买大礼包内所有物品的价格），或者大礼包内不包含任何的物品，那么购买这些大礼包不可能使整体价格降低。因此，我们可以不考虑这些大礼包，并将它们过滤掉，以提高效率和方便编码。
因为题目规定了「不能购买超出购物清单指定数量的物品」，所以只要我们购买过滤后的大礼包，都一定可以令整体价格降低。
class Solution {
Map<List<Integer>, Integer> memo = new HashMap<List<Integer>, Integer>();
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int n = price.size();
// 过滤不需要计算的大礼包，只保留需要计算的大礼包
List<List<Integer>> filterSpecial = new ArrayList<List<Integer>>();
for (List<Integer> sp : special) {
int totalCount = 0, totalPrice = 0;
for (int i = 0; i < n; ++i) {
totalCount += sp.get(i);
totalPrice += sp.get(i) * price.get(i);
}
if (totalCount > 0 && totalPrice > sp.get(n)) {
filterSpecial.add(sp);
}
}
return dfs(price, special, needs, filterSpecial, n);
}
// 记忆化搜索计算满足购物清单所需花费的最低价格
public int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> curNeeds, List<List<Integer>> filterSpecial, int n) {
if (!memo.containsKey(curNeeds)) {
int minPrice = 0;
for (int i = 0; i < n; ++i) {
minPrice += curNeeds.get(i) * price.get(i); // 不购买任何大礼包，原价购买购物清单中的所有物品
}
for (List<Integer> curSpecial : filterSpecial) {
int specialPrice = curSpecial.get(n);
List<Integer> nxtNeeds = new ArrayList<Integer>();
for (int i = 0; i < n; ++i) {
if (curSpecial.get(i) > curNeeds.get(i)) { // 不能购买超出购物清单指定数量的物品
break;
}
nxtNeeds.add(curNeeds.get(i) - curSpecial.get(i));
}
if (nxtNeeds.size() == n) { // 大礼包可以购买
minPrice = Math.min(minPrice, dfs(price, special, nxtNeeds, filterSpecial, n) + specialPrice);
}
}
memo.put(curNeeds, minPrice);
}
return memo.get(curNeeds);
}
}
18.4Sum
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]
题解：
类似双指针但是由于扩展到了4位，肯定不再考虑使用4指针标注的方式来遍历，与之相反的是，我们采取双循环加剩余部分双指针的策略来解决。
Maximum Product of Words length
Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.
Example 1:Input: words = [“abcw”,”baz”,”foo”,”bar”,”xtfn”,”abcdef”] Output: 16 Explanation: The two words can be “abcw”, “xtfn”.
Example 2:Input: words = [“a”,”ab”,”abc”,”d”,”cd”,”bcd”,”abcd”] Output: 4 Explanation: The two words can be “ab”, “cd”.
Example 3:Input: words = [“a”,”aa”,”aaa”,”aaaa”] Output: 0 Explanation: No such pair of words.
Constraints:
2 <= words.length <= 10001 <= words[i].length <= 1000words[i]consists only of lowercase English letters.
public int maxProduct(String[] words) {
int[] mask = new int[words.length];
int max = 0;
for(int i= 0;i< words.length;i++){
for(int j = 0;j < words[i].length();j++){
mask[i] |= 1 << (words[i].charAt(j) - 'a');
}
}
for(int i = 0;i < words.length;i++){
for(int j = i + 1;j < words.length;j++){
if((mask[i] & mask[j]) == 0){
max = Math.max(max,words[i].length() * words[j].length());
}
}
}
return max;
}双指针判断链表环问题
解题思路：
这类链表题目一般都是使用双指针法解决的，例如寻找距离尾部第 K 个节点、寻找环入口、寻找公共尾部入口等。
在本题的求解过程中，双指针会产生两次“相遇”。
双指针的第一次相遇：
- 设两指针
fast，slow指向链表头部head。 - 令
fast每轮走 222 步，slow每轮走 111 步。
执行以上两步后，可能出现两种结果：
第一种结果： fast 指针走过链表末端，说明链表无环，此时直接返回 null。
如果链表存在环，则双指针一定会相遇。因为每走 111 轮，fast 与 slow 的间距 +1+1+1，fast 一定会追上 slow 。
第二种结果： 当fast == slow时， 两指针在环中第一次相遇。下面分析此时 fast 与 slow 走过的步数关系：
设链表共有 a+ba+ba+b 个节点，其中 链表头部到链表入口 有 aaa 个节点（不计链表入口节点）， 链表环 有 bbb 个节点（这里需要注意，aaa 和 bbb 是未知数，例如图解上链表 a=4a=4a=4 , b=5b=5b=5）；设两指针分别走了 fff，sss 步，则有：
fast走的步数是slow步数的 222 倍，即 f=2sf = 2sf=2s；（解析：fast每轮走 222 步）fast比slow多走了 nnn 个环的长度，即 f=s+nbf = s + nbf=s+nb；（ 解析： 双指针都走过 aaa 步，然后在环内绕圈直到重合，重合时fast比slow多走 环的长度整数倍 ）。
将以上两式相减得到 f=2nbf = 2nbf=2nb，s=nbs = nbs=nb，即 fast 和 slow 指针分别走了 2n2n2n，nnn 个环的周长。
RMQ(Range maximum/minimum Queue)
239.滑动窗口最大值
TAG
「优先队列（堆）」、「线段树」、「分块」、「单调队列」、「RMQ」
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值 。
示例
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
很显然，题目表述的含义就是RMQ问题，首先我们考虑的事优先队列（大根堆），以（idx,num_idx）的方式入队
当下标达到首个滑动窗口的右端点后，每次尝试从优先队列（大根堆）中取出最大值（若堆顶元素的下标小于当前滑动窗口左端点时，则丢弃该元素）。
优先队列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->b[1]-a[1]);
int n = nums.length, m = n - k + 1, idx = 0;
int[] ans = new int[m];
for (int i = 0; i < n; i++) {
q.add(new int[]{i, nums[i]});
if (i >= k - 1) {
while (q.peek()[0] <= i - k) q.poll();
ans[idx++] = q.peek()[1];
}
}
return ans;
}
}
//Java线段树
线段树是什么？？线段树怎么写？？
如果你在考提高组前一天还在问这个问题，那么你会与一等奖失之交臂；如果你还在冲击普及组一等奖，那么这篇博客会浪费你人生中宝贵的5~20分钟。
上面两句话显而易见，线段树这个数据结构是一个从萌新到正式OI选手的过渡，是一个非常重要的算法，也是一个对于萌新来说较难的算法。不得不说，我学习了这个算法5遍左右才有勇气写的这篇博客。
但是，对于OI正式选手来说，线段树不是算法，应该是一种工具。她能把一些对于区间（或者线段）的修改、维护，从O(N)的时间复杂度变成O（logN）。
简单定义：线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。比如说一个长度为4的线段，我们可以表示成这样：
这是什么意思呢？ 如果你要表示线段的和，那么最上面的根节点的权值表示的是这个线段 1 ∼ 4 的和。根的两个儿子分别表示这个线段中 1 ∼ 2的和，与 3 ∼ 4 的和。以此类推。
然后我们还可以的到一个性质：节点 i 的权值 =她的左儿子权值 + 她的右儿子权值。因为 1 ∼ 4 的和就是等于 1 ∼ 2 的和与 2 ∼ 3 的和的和。
根据这个思路，我们就可以建树了，我们设一个结构体 tree，tree[i].l 与 tree[i].r 分别表示这个点代表的线段的左右下标，tree[i].sum 表示这个节点表示的线段和。
void build(int s, int t, int p) {
// 对 [s,t] 区间建立线段树,当前根的编号为 p
if (s == t) {
d[p] = a[s];
return;
}
int m = s + ((t - s) >> 1);
// 移位运算符的优先级小于加减法，所以加上括号
// 如果写成 (s + t) >> 1 可能会超出 int 范围
build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
// 递归对左右区间建树
d[p] = d[p * 2] + d[(p * 2) + 1];
}
简单线段树（无pushdown）
单点修改，区间查询
其实这一章开始才是真正的线段树，我们要用线段树干什么？答案是维护一个线段（或者区间），比如你想求出一个 1 ∼ 100 区间中， 4 ∼ 67 这些元素的和，你会怎么做？朴素的做法是for(i=4;i<=67;i++) sum+=a[i]，这样固然好，但是算得太慢了。
我们想一种新的方法，先想一个比较好画图的数据，比如一个长度为 4 的区间，分别是 1 、 2 、 3 、 4 ，我们想求出第 1 ∼ 3 项的和。按照上一部说的，我们要建出一颗线段树，其中点权（也就是红色）表示和：
我们总结一下，线段树的查询方法：
- 如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
- 如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
- 如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
inline int search(int i,int l,int r){
if(tree[i].l>=l && tree[i].r<=r)//如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
return tree[i].sum;
if(tree[i].r<l || tree[i].l>r) return 0;//如果这个区间和目标区间毫不相干，返回0
int s=0;
if(tree[i*2].r>=l) s+=search(i*2,l,r);//如果这个区间的左儿子和目标区间又交集，那么搜索左儿子
if(tree[i*2+1].l<=r) s+=search(i*2+1,l,r);//如果这个区间的右儿子和目标区间又交集，那么搜索右儿子
return s;
}关于那几个if的条件一定要看清楚，最好背下来，以防考场上脑抽推错。
然后,我们怎么修改这个区间的单点，其实这个相对简单很多，你要把区间的第dis位加上k。
那么你从根节点开始，看这个dis是在左儿子还是在右儿子，在哪往哪跑，
然后返回的时候，还是按照tree[i].sum=tree[i*2].sum+tree[i*2+1].sum的原则，更新所有路过的点
如果不理解，我还是画个图吧，其中深蓝色是去的路径，浅蓝色是返回的路径，回来时候红色的+标记就是把这个点加上这个值。
inline void add(int i,int dis,int k){
if(tree[i].l==tree[i].r){//如果是叶子节点，那么说明找到了
tree[i].sum+=k;
return ;
}
if(dis<=tree[i*2].r) add(i*2,dis,k);//在哪往哪跑
else add(i*2+1,dis,k);
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//返回更新
return ;
}
区间修改，单点查询
区间修改和单点查询，我们的思路就变为：如果把这个区间加上 k ，相当于把这个区间涂上一个 k 的标记，然后单点查询的时候，就从上跑到下，把沿路的标记加起来就好。
这里面给区间贴标记的方式与上面的区间查找类似，原则还是那三条，只不过第一条：如果这个区间被完全包括在目标区间里面，直接返回这个区间的值变为了如果这个区间如果这个区间被完全包括在目标区间里面，讲这个区间标记 k
void modify(int p, int l, int r, int k)
{
if(tr[p].l >= l && tr[p].r <= r) {
tr[p].num += k;
return ;
}
int mid = tr[p].l + tr[p].r >> 1;
if(l <= mid) modify(p << 1, l, r, k);
if(r > mid) modify(p << 1 | 1, l, r, k);
}
/*
inline void add(int i,int l,int r,int k){
if(tree[i].l>=l && tree[i].r<=r){//如果这个区间被完全包括在目标区间里面，讲这个区间标记k
tree[i].sum+=k;
return ;
}
if(tree[i*2].r>=l)
add(i*2,l,r,k);
if(tree[i*2+1].l<=r)
add(i*2+1,l,r,k);
}
*/
