首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    【题解】求区间和

    题目描述 给定 n 个正整数组成的数列 a1,a2,⋯ ,an 和 m 个区间 图片 分别求这 m 个区间的区间和。对于所有测试数据, 图片 输入格式 共 n+m+2 行。...输入输出样例 输入 #1 4 4 3 2 1 2 1 4 2 3 输出 #1 10 5 说明/提示 样例解释:第 1 到第 4 个数加起来和为 10。第 2 个数到第 3 个数加起来和为5。...对于 50% 的数据:n,m≤1000; 对于100% 的数据: 图片 题目分析 题目需要我们求出m个区间的和,现在已知每次询问的区间边界l和r。若采用暴力的方式,复杂度为O(nm) 。...可以采用前缀和的思想,先提前进行预处理。...){ int n,m,l,r; cin>>n; for(int i=1;i<=n;i++){//输入n个元素 cin>>a[i]; sum[i]=sum[i-1]+a[i];//维护前缀和,

    53220

    动态求连续区间和

    动态求连续区间和 给定 n 个数组成的一个数列,规定有两种操作,一是修改某个元素,二是求子数列 [a,b] 的连续和。 输入格式 第一行包含两个整数 n 和 m,分别表示数的个数和操作次数。...接下来 m 行,每行包含三个整数 k,a,b (k=0,表示求子数列[a,b]的和;k=1,表示第 a 个数加 b)。 数列从 1 开始计数。...输出格式 输出若干行数字,表示 k=0 时,对应的子数列 [a,b] 的连续和。...输出样例: 11 30 35 算法思路 1、lowbit(x):返回x的最后一位1 2、add(x,v):在x位置加上v,并将后面相关联的位置也加上v 3、query(x):询问x的前缀和...int mid = tr[u].l + tr[u].r >> 1; // 先计算下 当前这个区间 与[l, r]有没有交集 交集在那一部分 int sum = 0; // 区间[l, r]的和

    3200
    领券