K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
差值分析常用于处理多次区间修改、最终查询整体结果的场景，假设我们要对长度为n的数组执行k次区间增量操作，最后输出数组的所有元素。
使用差分数组解决该场景问题的总时间复杂度是O(n+k)，相比暴力法的O(nk)，在k远大于n时能显著提升运行效率
差分数组d的定义固定为d[i] = 原数组arr[i] - arr[i+1]，其中0≤i<n
差分数组只能处理区间加法操作，无法处理区间减法、区间乘法操作
执行区间[l, r]增加v的操作时，仅需要对差分数组执行d[l] += v这1步操作即可完成修改