线段树，树状数组专题

2019.7.16

线段树，树状数组专题

HDU 1166 敌兵布阵

单点更新，区间求和，树状数组模板题

#include <cstdio>
#include <cstring>

int bit[50010], n;

void add(int i, int x) {
    while(i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}
int sum(int y) {
    int s = 0;
    while(y > 0) {
        s += bit[y];
        y -= y & -y;
    }
    return s;
}

int main() {
    int t;
    scanf("%d", &t);
    for(int k = 1; k <= t; k++) {
        memset(bit, 0, sizeof(bit));
        printf("Case %d:
", k);
        int a;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a);
            add(i, a);
        }
        char b[10];
        int c, d;
        while(1) {
            scanf("%s", b);
            if(b[0] == 'E') break;
            else scanf("%d %d", &c, &d);
            if(b[0] == 'Q') printf("%d
", sum(d) - sum(c-1));
            else if(b[0] == 'A') add(c, d);
            else if(b[0] == 'S') add(c, -d);
        }
    }
    return 0;
}

POJ 3468 A Simple Problem with Integers

区间修改（加或减某个数），区间求和，树状数组模板题

#include <cstdio>
#define lowbit(i) (i & (-i))
typedef long long LL;
const LL Nmax = 200100;
LL N, Q;

LL delta[Nmax];
LL deltai[Nmax];
LL sum[Nmax];

LL Query(LL pos)
{
	LL temp = 0, tempp = 0, poss = pos + 1;
	while(pos > 0)
	{
		temp += delta[pos];
		tempp += deltai[pos];
		pos -= lowbit(pos);
	}
	return temp * poss - tempp;
}

void Update(LL pos, LL x)
{
    LL poss = x * pos;
	while(pos <= N)
	{
		delta[pos] += x;
		deltai[pos] += poss;
		pos += lowbit(pos);
	}
}

int main()
{
	scanf("%lld %lld", &N, &Q);
	LL x;
	for(LL i = 1; i <= N; ++i)
	{
		scanf("%lld", &x);
		sum[i] = sum[i - 1] + x;
	}
	while(Q--)
	{
		char sign[10];
		LL l, r, x;
		scanf("%s", sign);
		if(sign[0] == 'C')
		{
			scanf("%lld %lld %lld", &l, &r, &x);
			Update(l, x);
			Update(r+1, -x);
		}
		else
		{
		    scanf("%lld %lld", &l, &r);
			LL suml = sum[l - 1] + Query(l - 1);
			LL sumr = sum[r] + Query(r);
			printf("%lld
", sumr - suml);
		}
	}

	return 0;
}

HDU 4027 Can you answer these queries?（线段树）

有两种操作。第一种是对某个区间的数开根，第二种操作是查询某区间的和。

单点更新，区间求和，适当剪枝

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100000+50  ;
ll  sum[4*N], add[4*N] ;
void build(int l, int r, int i)
{
    sum[i] = 0;
    if(l == r)
    {
        scanf("%lld", &sum[i]);
        return ;
    }
    int mid = (l+r)>>1;
    build(l,mid,i<<1);
    build(mid+1,r,i<<1|1);
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
}
void update_sqrt(int i, int l, int r, int ql, int qr     ) //更新区间为qlqr,当前区间为l,r,代表当前区间和的节点为i，更新值为val,
{
    if(l > qr || ql > r)
        return ;
    if (l>=ql&&r<=qr&&sum[i]<=r-l+1)
        return ;
    if(l==r)
    {
        sum[i]=sqrt(1.0*sum[i]);
        return ;
    }
    int mid = (l + r) >> 1;
    update_sqrt(i << 1, l, mid, ql, qr  );
    update_sqrt(i << 1 | 1, mid + 1, r, ql, qr);
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
}
 
ll query(int i, int l, int r, int ql, int qr)     //查询区间为qlqr,当前区间为l,r,代表当前区间和的节点为i
{
    if(l > qr || ql > r)
        return 0;
    if(l >= ql && r <= qr)
        return sum[i];
    int mid =( l + r) >> 1;
    return query(i << 1, l, mid, ql, qr)
           + query(i << 1 | 1, mid + 1, r, ql, qr);
 
}
 
int main()
{
    int n,m;
    int cnt=1;
    while(scanf("%d", &n)!=EOF)
    {
        printf("Case #%d:
",cnt++);
        build(1,n,1);
        int m;
        cin>>m;
        int op;
        int a,b,c;
        for(  int i = 1; i <= m; i++)
        {
            scanf("%d",&op);
            if (op==1)
            {
                scanf("%d%d",&a,&b);
                if (a>b)swap(a,b);
                printf("%lld
",query(1, 1,n,a,b) );
            }
            else if (op==0)
            {
                scanf("%d%d",&a,&b);
                if (a>b)swap(a,b);
                update_sqrt(1,1,n,a,b);
            }
 
        }
        printf("
");
    }
    return 0;
}

HDU 1540
https://blog.csdn.net/qq_37383726/article/details/78321600

HDU 3974
https://blog.csdn.net/aqa2037299560/article/details/82829151