【LeetCode】线段树 segment-tree（共9题）+ 树状数组 binary-in

发布时间：2020-12-14 05:14:14 所属栏目：大数据来源：网络整理

导读：第一部分---线段树：https://leetcode.com/tag/segment-tree/?? 【218】The Skyline Problem ? 【307】Range Sum Query - Mutable ? 【308】Range Sum Query 2D - Mutable ? 【315】Count of Smaller Numbers After Self ? 【493】Reverse Pairs ? 【699】Fa

第一部分---线段树：https://leetcode.com/tag/segment-tree/??

【218】The Skyline Problem?

【307】Range Sum Query - Mutable?

【308】Range Sum Query 2D - Mutable?

【315】Count of Smaller Numbers After Self?

【493】Reverse Pairs?

【699】Falling Squares?

【715】Range Module?

【732】My Calendar III?

【850】Rectangle Area II?

第二部分---树状数组：https://leetcode.com/tag/binary-indexed-tree/

【218】The Skyline Problem?

【307】Range Sum Query - Mutable?（2019年1月14日，学习BIT）

实现一个一维的树状数组模板。

 1 class NumArray {
 2 public:
 3     NumArray(vector<int> nums) {
 4         n = nums.size();
 5         this->nums.resize(n+1);
 6         bit.resize(n+1);
 7         for (int i = 1; i <= n; ++i) {
 8             this->nums[i] = nums[i-1];
 9             add(i,this->nums[i]);
10         }      
11     }
12     void update(int i,int val) {
13         add(i+1,val - nums[i+1]);
14         nums[i + 1] = val;   
15     }
16     int sumRange(int i,int j) {
17         ++i,++j;
18         return sum(j) - sum(i-1);
19     }
20     int lowbit(int x) {
21         return x & -x;
22     }
23     void add(int x,int v) {
24         for (int i = x; i <= n; i += lowbit(i)) {
25             bit[i] += v;
26         }
27     }
28     int sum(int x) {
29         int ret = 0;
30         for (int i = x; i > 0; i -= lowbit(i)) {
31             ret += bit[i];
32         }
33         return ret;
34     }
35     vector<int> nums,bit;
36     int n;
37 };
38 
39 /**
40  * Your NumArray object will be instantiated and called as such:
41  * NumArray obj = new NumArray(nums);
42  * obj.update(i,val);
43  * int param_2 = obj.sumRange(i,j);
44  */

View Code

【308】Range Sum Query 2D - Mutable?（2019年1月14日，学习BIT）

【315】Count of Smaller Numbers After Self?(2019年1月22日，Fenwick Tree 练习)

给了一个数组 nums，返回一个数组，数组中的元素 ret[i] 代表 nums[i] 的右边有多少个比它小的数。（题目如果换一下，求每个元素左/右边有多少个比它小/大/大于等于/小于等于的数）

You are given an integer array?nums?and you have to return a new?counts?array. The?counts?array has the property where?counts[i]?is the number of smaller elements to the right of?nums[i].

Example:
Input: [5,2,6,1]
Output: [2,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

题解：这个题第一个想法是dp做，但是尝试了两下，完全推导不了。dp做不出来。看了下tag是树状数组，还有BST等等等很多种解法。我这次先练习下怎么用树状数组解题。

树状数组有两个用途（1）用 O(logN)的时间求前缀和。（2）用log(N)的时间在位置为 i 的元素上增加一个数。

这个题求数组中一个元素右边有多少个数比它小。我们如果翻转下数组，就可以变成求数组中一个元素左边有多少元素比它小。

那么它和 Fenwick Tree 有什么关系呢？

你想啊，我们可以把原数组先排序并且去重，得到一个递增的并且unique元素的新数组，但是呢这个新数组不能代表原来的数组，因为原来数组中可能有重复元素。所以我们搞出来一个 freq 数组(其实就是我们树状数组的原来数组)，配合sorted数组使用。

sorted数组里面的元素不是连续的，我们需要把它离散化，求出他们的相对位置。关系如下图：

nums:? ? ? [7,1,3,2,9,1]

sorted:? ? [1,7,9] （1-based）（其实就是我们元素对应树状数组的下标） sorted[nums[i]] = j

reversed: [1,7]

rank:? ? ? ?[1,5,4]

依次遍历 reversed 数组，先求这个元素前面有多少个元素小于它(树状数组的前缀和)，增加每个元素的 freq。往下求就ok了。

 1 class Solution {
 2 public:
 3     class FenwickTree {
 4     public:
 5         FenwickTree(int n): sums_(n+1,0) {}
 6         void add (int i,int delta) {
 7             while (i < sums_.size()) {
 8                 sums_[i] += delta;
 9                 i += lowbit(i);
10             }
11         }
12         int query (int i) {
13             int sum = 0;
14             while (i > 0) {
15                 sum += sums_[i];
16                 i -= lowbit(i);
17             }
18             return sum;
19         }
20     private:
21         static inline int lowbit(int x) {return x & -x;}
22         vector<int> sums_;
23     };
24     vector<int> countSmaller(vector<int>& nums) {
25         set<int> sorted(nums.begin(),nums.end());
26         unordered_map<int,int> rank;
27         int r = 0;
28         for (auto num : sorted) {
29             rank[num] = ++r;
30         }
31         vector<int> ret;
32         FenwickTree bit(rank.size());
33         for (int i = nums.size() - 1; i >= 0; --i) {
34             r = rank[nums[i]];
35             ret.push_back(bit.query(r-1));
36             bit.add(r,1);
37         }
38         reverse(ret.begin(),ret.end());
39         return ret;
40     }
41 };

View Code

【493】Reverse Pairs

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!