tree_array.c

数据结构中的树状数组,能够实现高效查询,在数组中进行查询的复杂度为 O(log(n

//-------树状数组-------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

__int64 in[100010];

int lowbit(int t)
{ 
    return t & (t^(t-1)); 
}

void modify(int pos,__int64 num)
{
	while (pos<=n)
	{
		in[pos]+=num;
		pos+=lowbit(pos);
	}
}

__int64 query(int end)
{
	__int64 sum=0;
	while (end>0)
	{
		sum+=in[end];
		end-=lowbit(end);
	}
	return sum;
}

__int64 com(int start , int end)
{
	return query(end)-query(start+1);
}

int main()
{
	int n,i,j;
	__int64 d;
	char ch;
	scanf("%d",&n);
	memset(in,0,sizeof(in));
	for(i=1;i<=n;i++)
	{
		scanf("%I64d",&d);
		modify(i,d);
	}
	while(1)
	{
		ch = getchar();
		while(ch != 'a' && ch != 'q' && ch != 'e')
			ch = getchar();
		if(ch == 'a')
		{
			scanf("%d%I64d",&i,&d);
			modify(i,d);
		}
		else if(ch == 'q')
		{
			scanf("%d%d",&i,&j);
			printf("%I64d\n",com(i,j));
		}
		else
		{
			break;
		}
	}
	return 0;	
}