前缀和

https://www.jianshu.com/p/89ec2814682c


入门

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前 n 项的和”。

前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。

设

b[]

为前缀和数组，

a[]

为原数组，根据这句话可以得到前缀和的定义式和递推式：

2055. 蜡烛之间的盘子

预处理 + 前缀和

右边界前蜡烛总数 – 左边界前蜡烛总数

• 时间复杂度：
  
  
  
  O

  (

  n

  +

  q

  )

  O(n+q)
  
  
  
  
  
  
  O
  
  
  (
  
  
  n
  
  
  
  
  +
  
  
  
  
  
  
  
  
  q
  
  
  )
  
  
  
  
  
  ，其中 n 为数组长度，q 为询问数量。我们需要 O(n) 的时间
  
  预处理
  
  。对于每一个
  
  询问
  
  ，我们需要 O(1) 的时间计算答案。

• 空间复杂度：
  
  
  
  O

  (

  n

  )

  O(n)
  
  
  
  
  
  
  O
  
  
  (
  
  
  n
  
  
  )
  
  
  
  
  
  ，其中 n 为数组长度。我们需要 O(n) 的空间保存预处理的结果。
  
  注意返回值不计入空间复杂度
  
  。

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.length();
        vector<int> nums(n);		// 保存当前位置前的盘子数量
        int sum = 0;
        for(int i = 0; i < n; ++i){
            if(s[i] == '*'){
                ++sum;
            }
            nums[i] = sum;
        }

        int l = -1;
        vector<int> left(n,-1);		// 当前位置右边第一根蜡烛的位置，即查询的左边界
        for(int i = n-1; i >= 0; --i){
            if(s[i] == '|'){
                l = i;
            }
            left[i] = l;
        }

        l = -1;
        vector<int> right(n,-1);	// 当前位置左边第一根蜡烛的位置，即查询的右边界
        for(int i = 0; i < n; ++i){
            if(s[i] == '|'){
                l = i;
            }
            right[i] = l;
        }

        int nn = queries.size();
        vector<int> ans(nn,0);		
        for(int i = 0; i < nn; ++i){		// 查询，取差
            int lx = left[queries[i][0]], rx = right[queries[i][1]];
            if(lx != -1 && rx != -1 && lx < rx){	
                ans[i] = nums[rx] - nums[lx];
            }
        }
        return ans;
    }
};