http://kenby.iteye.com/blog/962159
///我只想存个代码,思路来源解法都是上面那个网站看的
#include <stdio.h>
#include <string.h>
using namespace std;
const int N = 100000+10;
long long det[N],num[N],sum[N];
long long c1[N],c2[N];
int l,r,m,n;
char st[10];
int lowbit(int x)
{
return x&(-x);
}
void update(long long *array,int l,long long val)
{
while(l<=n)
{
array[l]+=val;
l+=lowbit(l);
}
}
long long getsum(long long *array,int l)
{
long long ans = 0;
while(l>0)
{
ans+=array[l];
l-=lowbit(l);
}
return ans;
}
int main()
{
int t;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&num[i]);
sum[i] = sum[i-1]+num[i];
}
while(m--)
{
scanf("%s",st);
if(st[0]=='C')
{
scanf("%d %d %d",&l,&r,&t);
update(c1,l,t);
update(c1,r+1,-t);
update(c2,l,t*l);
update(c2,r+1,-t*(r+1));
}
else
{
scanf("%d %d",&l,&r);
long long xx = 0;
xx = sum[r] - sum[l-1];
xx+= (r+1)*getsum(c1, r) - getsum(c2, r);
xx -= (l*getsum(c1, l-1) - getsum(c2, l-1));
printf("%lld\n",xx);
}
}
return 0;
}
分享到:
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
树状数组解决区间操作_高效 对数组的某个区间进行两种操作:1)求和 2)每个数据加常数。要求:时间复杂度低
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1747400
NULL 博文链接:https://128kj.iteye.com/blog/1745671
NULL 博文链接:https://128kj.iteye.com/blog/1746750
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
线段树、树状数组算法入门 加 poj解题报告 pdf文档
关于二部图、线段数、树状数组、树的分治的一些POJ题目的解答
7.4 树状数组 152 7.5 点树 154 7.6 STL 156 7.7 离散化 157 8.图论 158 8.0 2-SAT 158 8.2 寻找Euler回路 163 8.3 拓扑排序 163 8.4 差分约束系统 164 8.5 笛卡尔树 165 8.6 LCA和RMQ 167 8.7 割和桥 171 8.8 最小...
自己总结的一些算法代码模板,有基本的排序算法、图最短路径算法,也有树状数组、线段树这些骚操作. /nowcoder/coding-interviews/ 牛客网上《剑指offer》编程题C++代码,比该书的参考代码要简明许多,更加OJ风格. /...
1.5 后缀数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5.1 DA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5.2 DC3 . . . ...