行业-交易日 收益方块:矩形区间求和的批量查询
Sector-Day Return Cube: Batched Rectangular Range Sums
开始编码实现 solution(returns_matrix: list[list[float]], queries: list[list[int]]) -> list[float]。给定一个日度收益方块 returns_matrix[D][S](D 个交易日为行,S 个行业为列;每格为该行业当天的带符号十进制收益,例如 0.0123 表示 +1.23%),以及 Q 条矩形查询 queries,每条查询为四元组 [d_lo, d_hi, s_lo, s_hi],上下界均为闭区间(0 <= d_lo <= d_hi < D 且 0 <= s_lo <= s_hi < S)。返回长度为 Q 的浮点列表,第 k 个元素为第 k 条查询所对应矩形子块 returns_matrix[d_lo..d_hi][s_lo..s_hi] 内所有收益之和。
例:若 returns_matrix = [[0.01, -0.02, 0.005, 0.0], [0.012, 0.003, -0.01, 0.004], [-0.005, 0.0, 0.008, 0.002]],queries = [[0,1,0,1], [0,2,0,3]],第一条查询覆盖第 0..1 行、第 0..1 列,求和为 0.01 + (-0.02) + 0.012 + 0.003 = 0.005;第二条查询覆盖整个方块,求和为 0.009。
查询为空 (Q == 0) 时返回 []。空矩阵情形(D == 0 或 S == 0)只有在 Q == 0 时才是良定义的——按规范,对空方块发起查询的责任在调用方。
朴素逐查询双重循环每条 O(D*S),整体 O(Q*D*S) = 2*10^8 量级,会在隐藏大样本上超时;正解一次性构建 (D+1) x (S+1) 的二维前缀和索引,每条查询通过容斥在 O(1) 内回答。
实现细节由 stubs/stub.py 提供。
实践背景
多策略交易台收盘后会得到一个行业 × 交易日的收益方块,紧接着 PM 与风控会抛来大量临时性的矩形切片问题——"过去财报周科技板块的累计收益"、"三季度全部行业的合计"、"近五个交易日能源加材料"。会话循环里在方块加载时一次性构建二维前缀和索引(D*S <= 40000,开销可忽略),之后每个矩形聚合就是四次查表,便宜到分析师可以交互式地连发几千条切片问题,而不需要重跑内部求和。把索引预先建好与逐次惰性求和之间的差距,正是亚秒级切片与肉眼可感知卡顿之间的距离;同一招在交易台后续把视角拓到三维方块(日期 × 行业 × 因子)时也能直接复用。
约束条件
- 0 <= D <= 200 且 0 <= S <= 200,其中 D = len(returns_matrix);当 D > 0 时 S = len(returns_matrix[0])
- 0 <= Q <= 5000,其中 Q = len(queries)
- 每条查询为 [d_lo, d_hi, s_lo, s_hi],满足 0 <= d_lo <= d_hi < D 且 0 <= s_lo <= s_hi < S;上下界均为闭区间
- 每个 returns_matrix[i][j] 是带符号浮点数,绝对值不超过 1.0(十进制收益,例如 0.0123 表示 +1.23%)
- 输出为长度 Q 的浮点列表,按绝对误差 1e-9 比对;当 Q == 0 时返回 []
样例
Case 1 · statement-example: 3x4 matrix two queries
输入: [[[0.01,-0.02,0.005,0],[0.012,0.003,-0.01,0.004],[-0.005,0,0.008,0.002]],[[0,1,0,1],[0,2,0,3]]]
期望: [0.004999999999999999,0.009]
查询0=行0..1列0..1之和=0.01-0.02+0.012+0.003=0.005;查询1=整张表之和。
Case 2 · visible: single-cell query
输入: [[[0.05,-0.03],[0.02,0.01]],[[0,0,0,0],[1,1,1,1]]]
期望: [0.05,0.009999999999999995]
两次单格查询分别返回 m[0][0]=0.05 与 m[1][1]=0.01。
Case 3 · visible: empty queries returns empty list
输入: [[[0.01,0.02],[0.03,0.04]],[]]
期望: []
查询列表为空时返回空列表。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: 3x4 matrix two queries
输入: [[[0.01,-0.02,0.005,0],[0.012,0.003,-0.01,0.004],[-0.005,0,0.008,0.002]],[[0,1,0,1],[0,2,0,3]]]
期望: [0.004999999999999999,0.009]
查询0=行0..1列0..1之和=0.01-0.02+0.012+0.003=0.005;查询1=整张表之和。
Case 2 · visible: single-cell query
输入: [[[0.05,-0.03],[0.02,0.01]],[[0,0,0,0],[1,1,1,1]]]
期望: [0.05,0.009999999999999995]
两次单格查询分别返回 m[0][0]=0.05 与 m[1][1]=0.01。
Case 3 · visible: empty queries returns empty list
输入: [[[0.01,0.02],[0.03,0.04]],[]]
期望: []
查询列表为空时返回空列表。