POJ3468https://vjudge.net/problem/POJ-3468
學習了樹狀數組後看到書上還有關于它的區間更新知識點,書上給的不是很明确。我在網上找了一下發現了一種相對來說好了解的方法。在此總結。
因為初學,是以我要從頭回顧一下樹狀數組的知識點。
先說明lowit.在樹狀數組中lowbit是一個很重要的東西。他能清二進制數的高位1,保留最低位1.比如6->0110 ,用lowbit求出後得到了0010.常用的lowbit求法#define lowbit(x) (x&-x)
我把節點之間的關系定義為兩種,一種叫父子一種叫兄弟關系。
父子關系:
C5的父節點是C6,C6的父節點是C8,5->0101,6->0110,8->1000.子節點通過加上本身的lowbit值得到其父節點節點值。0101+0001=0110,0110+0010=1000.
這種關系用來更新某節點值。當5點更新,立刻通過他的lowbit找到父節點并更新直到不能更新為止。
void add(LL arr[],LL x, LL d){
while (x <= n){
arr[x] += d;
x += lowbit(x);
}
}
兄弟關系:
明日再更。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<set>
#include<vector>
#include<map>
#include<string>
#include<stdlib.h>
#include<limits.h>
using namespace std;
/******************************************************/
#define LL long long int
#define mem(a,b) memset(a,b,sizeof(a))
#define m ((l+r)/2)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define L rt<<1
#define R rt<<1|1
#define N 400000+1
#define pow(a) a*a
#define INF 0x3f3f3f3f
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define lowbit(x) (x&-x)
/*********************************************************/
/*sum[x] = org[]+...+org[x] + delta[]*x +
delta[]*(x-) + delta[]*(x-)+...+delta[x]*
= org[]+...+org[x] + segma(delta[i]*(x+-i))
= segma(org[i]) + (x+)*segma(delta[i]) - segma(delta[i]*i), <= i <= x*/
/***************************************************/
/*
Q
Q
Q
C
Q */
LL n, q;
LL dat[N];
LL summ[N];
LL bit0[N], bit1[N];
char s[];
void add(LL arr[],LL x, LL d){
while (x <= n){
arr[x] += d;
x += lowbit(x);
}
}
LL find(LL x,LL su[]){
LL res = ;
while (x > ){
res += su[x];
x -= lowbit(x);
}
return res;
}
int main(){
mem(summ, );
mem(bit0, );
mem(bit1, );
scanf("%lld%lld", &n, &q);
for (int i = ; i <= n; i++)scanf("%lld", &dat[i]);
summ[] = ;
for (int i = ; i <= n; i++){
summ[i] = summ[i - ] + dat[i];
}
while (q--){
LL a, b;
scanf("%s%lld%lld", s, &a, &b);
if (s[] == 'Q'){
LL sum = summ[b] - summ[a - ];
LL sum1 =(b+)* find(b, bit0) - find(b, bit1);
LL sum2 = a*(find(a - , bit0)) - find(a - , bit1);
printf("%lld\n", sum + sum1 - sum2);
}
else{
LL c; scanf("%lld", &c);
add(bit0, a, c);
add(bit0, b + , -c);
add(bit1, a, c*a);
add(bit1, b + , -c*(b + ));
}
}
}