网络前缀长度是什么是数组前缀和

来源：蜘蛛抓取(WebSpider) 时间：2012-05-27 04:16 标签： qq备注前缀
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
词典与后缀数组相结合的中文分词方法[权威资料]
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋后缀数组_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
上传于||暂无简介
阅读已结束，如果下载本文需要使用
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩9页未读，继续阅读
你可能喜欢poj 3468 树状数组解法 - The time is passing - ITeye技术网站
博客分类：
树状数组天生用来动态维护数组前缀和，其特点是每次更新一个元素的值，查询只能查数组的前缀和，
但这个题目求的是某一区间的数组和，而且要支持批量更新某一区间内元素的值，怎么办呢？实际上，
还是可以把问题转化为求数组的前缀和。
首先，看更新操作update(s, t, d)把区间A[s]...A[t]都增加d，我们引入一个数组delta[i]，表示
A[i]...A[n]的共同增量，n是数组的大小。那么update操作可以转化为：
1）令delta[s] = delta[s] + d，表示将A[s]...A[n]同时增加d，但这样A[t+1]...A[n]就多加了d，所以
2）再令delta[t+1] = delta[t+1] - d，表示将A[t+1]...A[n]同时减d
然后来看查询操作query(s, t)，求A[s]...A[t]的区间和，转化为求前缀和，设sum[i] = A[1]+...+A[i]，则
A[s]+...+A[t] = sum[t] - sum[s-1]，
那么前缀和sum[x]又如何求呢？它由两部分组成，一是数组的原始和，二是该区间内的累计增量和, 把数组A的原始
值保存在数组org中，并且delta[i]对sum[x]的贡献值为delta[i]*(x+1-i)，那么
sum[x] = org[1]+...+org[x] + delta[1]*x + delta[2]*(x-1) + delta[3]*(x-2)+...+delta[x]*1
= org[1]+...+org[x] + segma(delta[i]*(x+1-i))
= segma(org[i]) + (x+1)*segma(delta[i]) - segma(delta[i]*i)，1 &= i &= x
这其实就是三个数组org[i], delta[i]和delta[i]*i的前缀和，org[i]的前缀和保持不变，事先就可以求出来，delta[i]和
delta[i]*i的前缀和是不断变化的，可以用两个树状数组来维护。
树状数组的解法比朴素线段树快很多，如果把long long变量改成__int64，然后用C提交的话，可以达到1047ms，
排在22名，但很奇怪，如果用long long变量，用gcc提交的话就要慢很多。
#include &stdio.h&
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#define debug(...)
#define N 100002
#define lowbit(i) ( i & (-i) )
/* 设delta[i]表示[i,n]的公共增量 */
long long c1[N]; /* 维护delta[i]的前缀和 */
long long c2[N]; /* 维护delta[i]*i的前缀和 */
long long sum[N];
long long query(long long *array, int i)
while (i & 0) {
tmp += array[i];
i -= lowbit(i);
void update(long long *array, int i, long long d)
while (i &= n) {
array[i] +=
i += lowbit(i);
int main()
q, i, s, t,
scanf("%d %d", &n, &q);
for (i = 1; i &= i++) {
scanf("%d", A+i);
for (i = 1; i &= i++) {
sum[i] = sum[i-1] + A[i];
while (q--) {
getchar();
scanf("%c %d %d", &action, &s, &t);
if (action == 'Q') {
ans = sum[t] - sum[s-1];
ans += (t+1)*query(c1, t) - query(c2, t);
ans -= (s*query(c1, s-1) - query(c2, s-1));
printf("%lld\n", ans);
scanf("%d", &d);
/* 把delta[i](s&=i&=t)加d，策略是
*先把[s,n]内的增量加d，再把[t+1,n]的增量减d
update(c1, s, d);
update(c1, t+1, -d);
update(c2, s, d*s);
update(c2, t+1, -d*(t+1));
事实上,还可以不通过求s和t的前缀和，而是直接求出[s,t]的区间和，这是因为：
sum[t] = segma(org[i]) + (x+1)*segma(delta[i]) - segma(delta[i]*i)
1 &= i &= t
sum[s-1] = segma(org[i]) + s*segma(delta[i]) - segma(delta[i]*i)
1 &= i &= s-1
[s,t]的区间和可以表示为：
sum[t]-sum[s-1] = org[s] + ... + org[t] + (t+1)*(delta[s] + ... + delta[t]) + (t-s+1)*(delta[1] + ... + delta[s-1])
- (delta[s]*s + ... + delta[t]*t)
= segma(org[i]) +(t+1)* segma(delta[i]) - segma(delta[i]*i) , s &= i &= t
+ (t-s+1)*segma(delta[i]), 1 &= i &= s-1
问题转化为求三个数组org, delta[i]和delta[i]*i的区间和，而线段树可以直接求出区间和，所以又得到了另外一种
#include &stdio.h&
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#define debug(...)
#define N 100002
/* 设delta[i]表示[i,n]的公共增量 */
long long tree1[262144]; /* 维护delta[i]的前缀和 */
long long tree2[262144]; /* 维护delta[i]*i的前缀和 */
long long sum[N];
/* 查询[s,t]的区间和 */
long long query(long long *tree, int s, int t)
for (s = s+M-1, t = t+M+1; (s^t) != 1; s &&= 1, t &&= 1) {
if (~s&1) {
tmp += tree[s^1];
if (t&1) {
tmp += tree[t^1];
/* 修改元素i的值 */
void update(long long *tree, int i, long long d)
for (i = (i+M); i & 0; i &&= 1) {
tree[i] +=
int main()
q, i, s, t,
scanf("%d %d", &n, &q);
for (i = 1; i &= i++) {
scanf("%d", A+i);
for (i = 1; i &= i++) {
sum[i] = sum[i-1] + A[i];
for (M = 1; M & (n+2); M &&= 1);
while (q--) {
getchar();
scanf("%c %d %d", &action, &s, &t);
if (action == 'Q') {
ans = sum[t] - sum[s-1];
ans += (t+1)*query(tree1, s, t)+(t-s+1)*query(tree1, 1, s-1);
ans -= query(tree2, s, t);
printf("%lld\n", ans);
scanf("%d", &d);
/* 把delta[i](s&=i&=t)加d，策略是
*先把[s,n]内的增量加d，再把[t+1,n]的增量减d
update(tree1, s, d);
update(tree2, s, d*s);
if (t & n) {
update(tree1, t+1, -d);
update(tree2, t+1, -d*(t+1));
两种解法本质上是一样的，其实zkw式线段树 == 树状数组，它们都可以支持查询某个区间的和，以及修改某个点的值，
但不能直接修改某个区间的值，必须引入一个额外的数组，如这题的delta数组，把对区间的修改转化为对两个端点的修改。
浏览: 334952 次
来自: 北京
写的不错，很透彻
好，赞扬！
赞一个~！ ，现在正在看redis 所以接触到跳表
vote--后还要判断是否为0吧，如果为0则废掉重新置位can ...
树状数组不是求前缀和的吗？那那个detial数组是怎么回事啊

我要回帖

更多关于 qq备注前缀 的文章

 

随机推荐