AcWing 242 一个简单整数问题(区间修改单点查询)

2021-03-17 08:24

阅读：363

标签：oid 思想 printf for cin ble == scanf 前缀

原题
该题涉及树状数组又一串操作：

① 区间修改
运用差分的思想，我们新建了一个数组b，初始化为零，对于每个指令"C l r d",我们只需将其转化为以下操作：
1.把b[l]加上d
2.再把b[r+1]减去d

inline void add(int x,int y)
{
   for(;x

    add(l,j);
    add(r+1,-j);

② 单点查询
执行了以上操作后，b数组的前缀和b[1~x]就代表了该指令对a[x]的影响，而在查询指令"Q x"中，我们只需查询前缀和b[1~x],最后再加上a[x]即可

inline int ask(int x)
{
   int ans=a[x];
   for(;x;x-=x&-x)
   {
      ans+=c[x];
   }
   return ans;
}

AC代码：

#include
using namespace std;
int n,m,a[100005],c[100005];
inline int ask(int x)
{
   int ans=a[x];
   for(;x;x-=x&-x)
   {
      ans+=c[x];
   }
   return ans;
}
inline void add(int x,int y)
{
   for(;x>n>>m;
    for(int i=1;i

做了这题，发现自己代码能力好差，找bug找了好久。
这题用了内联函数，发现也没快多少2333

AcWing 242 一个简单整数问题(区间修改单点查询)

标签：oid 思想 printf for cin ble == scanf 前缀

原文地址：https://www.cnblogs.com/Pecoz/p/12397315.html

上一篇：Windows 10 神州网信政府版麦克风、摄像头的使用。

下一篇：C# 实践 2 async 关键字

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 242 一个简单整数问题(区间修改单点查询)
文章链接：http://soscw.com/index.php/essay/65221.html

亲，登录后才可以留言！

AcWing 242 一个简单整数问题(区间修改单点查询)

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing 242 一个简单整数问题(区间修改 单点查询)

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing 242 一个简单整数问题(区间修改单点查询)