我还是喜欢用分块!
虽然我第一次是交的树状数组
我的题库:https://blog.csdn.net/L_Y_T020321/article/details/83152606
比较惊奇的是,luogu题解里有写线段树的,有写树状数组的,就连模拟的都有!!!
题目描述
给定一个长度为n(n<=100000),初始值都为0的序列,x(x<=10000)次的修改某些位置上的数字,每次加上一个数,然后提出y (y<=10000)个问题,求每段区间的和。时间限制1秒。
输入输出格式
输入格式:
第一行1个数,表示序列的长度n
第二行1个数,表示操作的次数w
后面依次是w行,分别表示加入和询问操作
其中,加入用x表示,询问用y表示
x的格式为"x a b" 表示在序列a的位置加上b
y的格式为"y a b" 表示询问a到b区间的加和
输出格式:
每行一个数,分别是每次询问的结果
输入输出样例
输入样例#1:
5
4
x 3 8
y 1 3
x 4 9
y 3 4
输出样例#1:
8
17
所以,我就来发一个分块的题解
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 200000
using namespace std ;
int n , N , a[maxn] , s[maxn] ;
int pos[maxn] ,tag[maxn],m;
void update(int x , int y , int k) {//区间加法(不是单点么?都一样了)
for(int i = x ; i <= min(pos[x]*N,y) ; i ++) {
a[i] += k ;
s[pos[x]] += k ;
}
if(pos[x]!=pos[y]) {
for(int i = (pos[y]-1)*N+1;i<=y;i++) {
a[i] += k ;
s[pos[y]] += k ;
}
}
for(int i = pos[x]+1;i<=pos[y]-1;i ++) tag[i] += k ;
}
int query(int x , int y) {//区间求和
long long ans = 0 ;
for(int i = x ; i <= min (pos[x]*N,y) ; i ++) {
ans += a[i] + tag[pos[x]] ;
}
if(pos[x] != pos[y]) {
for(int i = (pos[y]-1)*N+1;i<=y;i ++) {
ans += a[i] + tag[pos[y]] ;
}
}
for(int i = pos[x]+1;i<=pos[y]-1;i++) ans += s[i] + tag[i]*N ;
return ans ;
}
int main() {
cin >> n >> m ;
N = sqrt(n) ;
for(int i = 1 ; i <= n ; i ++) {
pos[i] = (i-1)/N + 1 ;
}
for(int i = 1 ; i <= m ; i ++) {
char opt ;int x , y , z ;
cin >> opt ;
if(opt == 'x') {
cin >> x >> z ;
update(x,x,z) ;//区间(单点)加
}else {
cin >> x >>y ;
cout << query(x,y) << endl;//区间求和
}
}
return 0 ;
}
分块真神奇!!
写这么多的分块会被打吧QAQ
在放一个树状数组(0注释)
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lowbit(x) x&(-x)
#define maxn 500010
using namespace std ;
int n , m ;
int a[maxn] ;
int read() {
long long x = 0 ;int f = 1 ; char s = getchar() ;
while(s>'9' || s < '0') {if(s == '-') f = -1 ; s = getchar() ; }
while(s<='9'&&s>='0') {x=x*10+(s-'0') ; s = getchar() ;}
return x * f ;
}
void update(int x , int k ) {
for(int i = x ; i <= n ; i += lowbit(i)) {
a[i] += k ;
}
}
int query(int x ) {
long long res = 0 ;
for(int i = x ; i ; i -= lowbit(i) ) {
res += a[i] ;
}
return res ;
}
int main() {
n = read() , m = read() ;
for(int i = 1 ; i <= n ; i ++) {
int x ;
update(i,0) ;
}
for(int i = 1 ; i <= m ; i ++) {
char opt ;
int x , y , z ;
//opt = read() ;
cin >> opt ;
if(opt == 'x') {
x = read() , y = read() ;
update(x,y) ;
}else {
x = read() , y = read() ;
cout << query(y) - query(x-1) <<endl ;
}
}
return 0 ;
}
完结散花!!!