https://selfboot.cn/2016/07/24/leetcode_guide_why/
Given an array of size N which is initialized with all zeros. We are given many range add queries, which should be applied to this array. We need to print final updated array as our result.
This problem can be solved using segment tree with lazy updates in O(log N) time per query but we can do better here, as update operation is not given. We can process each query in constant time using this logic, when a query to add V is given in range [a, b] we will add V to arr[a] and –V to arr[b+1] now if we want to get the actual values of array we will convert the above array into prefix sum array
So in effect, when we add a value V to specific index of array, It represents adding V to all elements right to this index, that is why we add –V after range to remove its effect after its range of add query.
波利亚用三本书：《How To Solve It》、《数学的发现》、《数学与猜想》）来试图阐明人类解决问题的一般性的思维方法，总结起来主要有以下几种：
时刻不忘未知量。即时刻别忘记你到底想要求什么，问题是什么。（动态规划中问题状态的设定）试错。对题目这里捅捅那里捣捣，用上所有的已知量，或使用所有你想到的操作手法，尝试着看看能不能得到有用的结论，能不能离答案近一步（回溯算法中走不通就回退）。求解一个类似的题目。类似的题目也许有类似的结构，类似的性质，类似的解方案。通过考察或回忆一个类似的题目是如何解决的，也许就能够借用一些重要的点子（比较 Ugly Number 的三个题目：263. Ugly Number， 264. Ugly Number II， 313. Super Ugly Number）。用特例启发思考。通过考虑一个合适的特例，可以方便我们快速寻找出一般问题的解。反过来推导。对于许多题目而言，其要求的结论本身就隐藏了推论，不管这个推论是充分的还是必要的，都很可能对解题有帮助。
刷 LeetCode 的最大好处就是可以锻炼解决问题的思维能力，相信我，如何去思考本身也是一个需要不断学习和练习的技能。
此外，大量高质量的题目可以加深我们对计算机科学中经典数据结构的
深刻理解，从而可以快速用合适的数据结构去解决现实中的问题。我们看到很多ACM大牛，拿到题目后立即就能想出解法，大概就是因为他们对于各种数据结构有着深刻的认识吧。LeetCode 上面的题目涵盖了几乎所有常用的数据结构：- Stack：简单来说具有后进先出的特性，具体应用起来也是妙不可言，可以看看题目 32. Longest Valid Parentheses。
- Linked List：链表可以快速地插入、删除，但是查找比较费时（具体操作链表时结合图会简单很多，此外要注意空节点）。通常链表的相关问题可以用双指针巧妙的解决，160. Intersection of Two Linked Lists 可以帮我们重新审视链表的操作。
- Hash Table：利用 Hash 函数来将数据映射到固定的一块区域，方便 O(1) 时间内读取以及修改。37. Sudoku Solver 数独是一个经典的回溯问题，配合 HashTable 的话，运行时间将大幅减少。
- Tree：树在计算机学科的应用十分广泛，常用的有二叉搜索树，红黑书，B+树等。树的建立，遍历，删除相对来说比较复杂，通常会用到递归的思路，113. Path Sum II 是一个不错的开胃菜。
- Heap：特殊的完全二叉树，“等级森严”，可以用 O(nlogn) 的时间复杂度来进行排序，可以用 O(nlogk) 的时间复杂度找出 n 个数中的最大（小）k个，具体可以看看 347. Top K Frequent Elements。
算法：时间空间
我们知道，除了数据结构，具体算法在一个程序中也是十分重要的，而算法效率的度量则是时间复杂度和空间复杂度。通常情况下，人们更关注时间复杂度，往往希望找到比 O( n^2 ) 快的算法，在数据量比较大的情况下，算法时间复杂度最好是O(logn)或者O(n)。计算机学科中经典的算法思想就那么多，LeetCode 上面的题目涵盖了其中大部分，下面大致来看下。
- 分而治之：有点类似“大事化小、小事化了”的思想，经典的归并排序和快速排序都用到这种思想，可以看看 Search a 2D Matrix II 来理解这种思想。
- 动态规划：有点类似数学中的归纳总结法，找出状态转移方程，然后逐步求解。 309. Best Time to Buy and Sell Stock with Cooldown 是理解动态规划的一个不错的例子。
- 贪心算法：有时候只顾局部利益，最终也会有最好的全局收益。122. Best Time to Buy and Sell Stock II看看该如何“贪心”。
- 搜索算法（深度优先，广度优先，二分搜索）：在有限的解空间中找出满足条件的解，深度和广度通常比较费时间，二分搜索每次可以将问题规模缩小一半，所以比较高效。
- 回溯：不断地去试错，同时要注意回头是岸，走不通就换条路，最终也能找到解决问题方法或者知道问题无解，可以看看 131. Palindrome Partitioning。
当然，还有一部分问题可能需要一些数学知识去解决，或者是需要一些位运算的技巧去快速解决。总之，我们希望找到时间复杂度低的解决方法。为了达到这个目的，我们可能需要在一个解题方法中融合多种思想，比如在 300. Longest Increasing Subsequence 中同时用到了动态规划和二分查找的方法，将复杂度控制在 O(nlogn)。如果用其他方法，时间复杂度可能会高很多，这种题目的运行时间统计图也比较有意思，可以看到不同解决方案运行时间的巨大差异，如下：
除了优秀的代码，有时候还会有直观的解题思路分享，方便看看别人是如何解决这个问题的。@MissMary在“两个排序数组中找出中位数”这个题目中，给出了一个很棒的解释：Share my o(log(min(m,n)) solution with explanation，获得了400多个赞。
你也可以评论大牛的代码，或者提出改进方案，不过有时候可能并非如你预期一样改进后代码会运行地更好。在 51. N-Queens 的讨论 Accepted 4ms c++ solution use backtracking and bitmask, easy understand 中，@binz 在讨论区中纳闷自己将数组 vector （取值非零即一）改为 vector 后，运行时间变慢。@prime_tang 随后就给出建议说最好不要用 vector，并给出了两个 StackOverflow 答案。
当你逛讨论区久了，你可能会有那么一两个偶像，比如@StefanPochmann。他的一个粉丝 @agave 曾经问 StefanPochmann 一个问题：
Hi Stefan, I noticed that you use a lot of Python tricks in your solutions, like “v += val,” and so on… Could you share where you found them, or how your learned about them, and maybe where we can find more of that? Thanks!
StefanPochmann 也不厌其烦地给出了自己的答案：
@agave From many places, though I’d say I learned a lot on CheckiO and StackOverflow (when I was very active there for a month). You might also find some by googling python code golf.
原来大神也是在 StackOverflow 上修炼的，看来需要在 为什么离不开 StackOverflow 中添加一个理由了：因为 StefanPochmann 都混迹于此。
类似这样友好，充满技术味道的讨论，在 LeetCode 讨论区遍地都是，绝对值得我们去好好探访。
http://www.geeksforgeeks.org/constant-time-range-add-operation-array/Given an array of size N which is initialized with all zeros. We are given many range add queries, which should be applied to this array. We need to print final updated array as our result.
This problem can be solved using segment tree with lazy updates in O(log N) time per query but we can do better here, as update operation is not given. We can process each query in constant time using this logic, when a query to add V is given in range [a, b] we will add V to arr[a] and –V to arr[b+1] now if we want to get the actual values of array we will convert the above array into prefix sum array
So in effect, when we add a value V to specific index of array, It represents adding V to all elements right to this index, that is why we add –V after range to remove its effect after its range of add query.
void add(int arr[], int N, int lo, int hi, int val){ arr[lo] += val; if (hi != N - 1) arr[hi + 1] -= val;}// Utility method to get actual array from operation arrayvoid updateArray(int arr[], int N){ // convert array into prefix sum array for (int i = 1; i < N; i++) arr[i] += arr[i - 1];}// method to print final updated arrayvoid printArr(int arr[], int N){ updateArray(arr, N); for (int i = 0; i < N; i++) cout << arr[i] << " "; cout << endl;}
