二维前缀和模板

前缀和总结

一维前缀和

对于一维前缀和模板，例如dp[i]表示某个字符串前i个中某个字符出现的次数，那么子串i到j中某个字符出现的次数为dp[j]-dp[i]

所以初始化dp的方法就是采用一次遍历，当str[i]==target，dp[i]=dp[i-1]+1，否则dp[i]=dp[i-1]，这样可以将查询的时间复杂度从N降到1

二维前缀和