其他
原来树状数组可以这么简单?
The following article is from 小K算法 Author 小K算法
点击关注公众号,一周多次包邮送书
01故事起源
02分析
03定义
return x & -x;
}
sum[i]等于区间[i-lowbit(i)+1,i]中所有元素的和。也就是从位置i开始,往前数lowbit(i)个元素,加起来就是sum[i]。
04规律
05单点修改
while (index <= n) {
sum[index] += x;
index += lowbit(index);
}
}
06区间查询
int ret = 0;
while (index > 0) {
ret += sum[index];
index -= lowbit(index);
}
return ret;
}
07区间修改
// 单个修改
void add(LL *sum, LL index, LL x) {
while (index <= n) {
sum[index] += x;
index += lowbit(index);
}
}
// 区间修改
void range_add(LL left, LL right, LL x) {
right++;
add(sum1, left, x);
add(sum1, right, -x);
add(sum2, left, x * left);
add(sum2, right, -x * right);
}
08区间查询
LL query(const LL *sum, LL index) {
LL ret = 0;
while (index > 0) {
ret += sum[index];
index -= lowbit(index);
}
return ret;
}
// 区间查询
LL range_query(LL left, LL right) {
left--;
LL sumA = (left + 1) * query(sum1, left) - query(sum2, left);
LL sumB = (right + 1) * query(sum1, right) - query(sum2, right);
return sumB - sumA;
}
09总结
推荐阅读
• 为什么要用读写锁?它有什么优点?• 微软继续拆分VS Code Python扩展,再推三款独立扩展• 聊聊 Java SPI 机制• JVM 八股之首:三大垃圾收集算法• React官方团队出手,补齐原生Hook短板• 这 6 个场景下 RocketMQ 会找不到 Broker• 引入『客户端缓存』,Redis6算是把缓存玩明白了…
👇更多内容请点击👇