当前位置: 首页 > news >正文

网站移动端是什么问题吗优帮云首页推荐

网站移动端是什么问题吗,优帮云首页推荐,湖北建设科技中心网站,wordpress 主题盗第五十七章 树状数组(二)一、差分的缺陷二、树状数组与差分三、例题题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示样例 1 解释:数据规模与约定代码一、差分的缺陷 差分的作用是能够在O(1)的时间内给一段区间加上相同的数字&am…

第五十七章 树状数组(二)

  • 一、差分的缺陷
  • 二、树状数组与差分
  • 三、例题
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 提示
        • 样例 1 解释:
        • 数据规模与约定
    • 代码

一、差分的缺陷

差分的作用是能够在O(1)的时间内给一段区间加上相同的数字,最终查询的时候, 只需要对差分数组求前缀和即可。
但是,如果我们修改一次就想查询一次某个点的值的话。就说明我们需要不断地去求前缀和,即我们每次查询的时间复杂度都是O(n)O(n)O(n)的。这个是非常低效的。

因此,我们就可以利用树状数组来进行优化求解。

二、树状数组与差分

作者在之前的文章中介绍过树状数组与前缀和的关系,没有看过的话,作者建议先去看之前的文章:第五十六章 树状数组(一)

在前缀和+树状数组的题目中,我们是将原数组包装成了树状数组。

而在差分+树状数组的题目中,我们需要将原数组的差分数组写作树状数组的形式。

这样的话,如果给原数组[l,r]内的元素加上一个x的话,我们只需要操作差分数组中的两个点即可。这就又转化为我们在之前的文章中介绍的树状数组的三个函数。

三、例题

洛谷:P3368 【模板】树状数组 2

题目描述

如题,已知一个数列,你需要进行下面两种操作:

  1. 将某区间每一个数加上 xxx

  2. 求出某一个数的值。

输入格式

第一行包含两个整数 NNNMMM,分别表示该数列数字的个数和操作的总个数。

第二行包含 NNN 个用空格分隔的整数,其中第 iii 个数字表示数列第 $i $ 项的初始值。

接下来 MMM 行每行包含 222444个整数,表示一个操作,具体如下:

操作 111: 格式:1 x y k 含义:将区间 [x,y][x,y][x,y] 内每个数加上 kkk

操作 222: 格式:2 x 含义:输出第 xxx 个数的值。

输出格式

输出包含若干行整数,即为所有操作 222 的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

样例输出 #1

6
10

提示

样例 1 解释:

故输出结果为 6、10。


数据规模与约定

对于 30%30\%30% 的数据:N≤8N\le8N8M≤10M\le10M10

对于 70%70\%70% 的数据:N≤10000N\le 10000N10000M≤10000M\le10000M10000

对于 100%100\%100% 的数据:1≤N,M≤5000001 \leq N, M\le 5000001N,M5000001≤x,y≤n1 \leq x, y \leq n1x,yn,保证任意时刻序列中任意元素的绝对值都不大于 2302^{30}230

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int a[N], b[N], tree[N];
int n, m;int lowbits(int x)
{return x & -x;
}void add(int pos, int x)
{for(int i = pos; i <= n; i += lowbits(i))tree[i] += x;
}int quary(int pos)
{int res = 0;for(int i = pos; i; i -= lowbits(i))res += tree[i];return res;
}void solve()
{cin >> n >> m;for(int i = 1; i <= n; i ++ )cin >> a[i];for(int i = 1; i <= n; i ++ ){b[i] = a[i] - a[i - 1];add(i, b[i]);}while(m -- ){int op;cin >> op;if(op == 1){int l, r, d;cin >> l >> r >> d;add(l, d);add(r + 1, -d);}else{int pos;cin >> pos;cout << quary(pos) << endl;}}}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}
http://www.ritt.cn/news/193.html

相关文章:

  • 手机网站案例网站建设制作过程
  • 在什么网站可以做外贸出口劳保鞋百度推广咨询
  • 吉林省四平市网站建设seo整站优化服务
  • 平台和网站有什么区别seo推广的特点
  • 营销型网站建设哪里济南兴田德润优惠吗百度问答官网
  • 我要学做网站推广网站seo
  • 网站建设广州潍坊seo推广
  • 什么是html5网站软文内容
  • wordpress 导航下拉优化设计六年级下册语文答案
  • 旅游网站开发 目的及必要性google网站
  • 创可贴在线设计网站大数据分析营销平台
  • 广州注册公司在哪个网站广西南宁市有公司网站设计
  • 用dw做教学网站cctv 13新闻频道
  • 做恶搞网站软件上海百度seo
  • 如何建立属于自己的网址重庆企业seo
  • 请问聊城网站建设淘宝seo搜索引擎原理
  • 中国建设银行网站地图品牌策划公司
  • 网站建设公司发展理念seo整站优化更能准确获得客户
  • 十堰做网站公司湖南关键词排名推广
  • 专门做焦点图的网站营销推广计划怎么写
  • 找做网站的人深圳优化网站方法
  • 国家网站域名宁波关键词优化排名工具
  • wordpress图片左对齐seo有哪些网站
  • 陕西省住房城乡建设厅网站管理中心在运营中seo是什么意思
  • 怎么做网站收广告费杭州网络推广外包
  • 宁波网站搜索引擎优化十大免费货源网站免费版本
  • 网站盈利方法网站seo外包
  • 如何仿制国外网站山西网页制作
  • 国家建设局网站品牌推广思路
  • 陈江做网站深圳seo秘籍