前言
七月初3000分时曾在群里立过flag，后来有几场运气手速都比较好，侥幸成功。陆续又挣扎了几个月尝试着冲3200分，发现以我现在的水平差得还很远，索性先整理好学习算法接近两年来的一些py常用模板，分享给大家。
新鲜出炉的public地址
借用hls的id起的project name
https://github.com/liupengsay/PyIsTheBestLang
食用方式
其实很简单，每个算法子类都有
-
template.py 主要是一些封装类class模板，比如树状数组的一些模板
-
example.py 主要是上述封装类class的测试用例，比如树状数组的一些模板测试用例
-
problem.py 主要是各平台尤其是力扣的题目以及使用上述封装类class的题目链接和代码，比如树状数组相关的题目链接和代码
赛题举例
以第370场周赛T4平衡子序列的最大和举例
使用三个板子进行离散化树状数组查询
模板一：树状数组
from math import inf
from typing import List
from src.data_structure.tree_array.template import PointAscendRangeMax
class Solution:
def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
# 树状数组（单点持续更新为更大值）（区间查询最大值）2380ms
n = len(nums)
tmp = [nums[i] - i for i in range(n)]
ind = sorted(list(set(tmp)))
dct = {x: i for i, x in enumerate(ind)}
tree = PointAscendRangeMax(n, -inf)
for j in range(n):
num = nums[j]
i = dct[num - j]
pre = tree.range_max(1, i + 1) if i + 1 >= 1 else 0
pre = 0 if pre < 0 else pre
tree.point_ascend(i + 1, pre + num)
return tree.range_max(1, n)模板二：树状数组
from typing import List
from src.data_structure.tree_array.template import PointAscendPreMax
class Solution:
def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
# 树状数组（单点持续更新为更大值）（前缀区间查询最大值）1748ms
n = len(nums)
tmp = [nums[i] - i for i in range(n)]
ind = sorted(list(set(tmp)))
dct = {x: i for i, x in enumerate(ind)}
tree = PointAscendPreMax(n)
for j in range(n):
num = nums[j]
i = dct[num - j]
pre = tree.pre_max(i + 1)
pre = 0 if pre < 0 else pre
tree.point_ascend(i + 1, pre + num)
return tree.pre_max(n)模板三：线段树
from typing import List
from src.data_structure.segment_tree.template import RangeAscendRangeMax
class Solution:
def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
# 线段树（单点持续更新为更大值）（区间查询最大值）7980ms
n = len(nums)
tmp = [nums[i] - i for i in range(n)]
ind = sorted(list(set(tmp)))
dct = {x: i for i, x in enumerate(ind)}
tree = RangeAscendRangeMax(n)
for j in range(n):
num = nums[j]
i = dct[num - j]
pre = tree.range_max(0, i)
pre = 0 if pre < 0 else pre
tree.range_ascend(i, i, pre + num)
ans = tree.range_max(0, n - 1)
return ans结束
算法学习至今，水平仍旧有限，希望这个分享能帮助大家。另外有部分模板是从一些选手比如草莓🍓、灵神等的题解或者网上抄录整理得来的，未能全部注明还望海涵。欢迎有效交流共同进步。祝py选手做大做强，祝力扣周周有赞助，祝所有同行都能快乐工作幸福生活。
评论 (27)
