hdu 1166 树状数组 & 线段树

//树状数组
#include "stdafx.h"
#include <iostream>
using namespace std;

const int MAXN = 50010;
int num[MAXN];
int sum[MAXN];//sum[i]: lowbit为i的二进制表示中右边第一个1所代表的数字,然后sum[i]里存的就是从num[i]开始向前数lowbit个元素之和
int n;

int lowbit(int x) //取x的最低位
{
	return x&(-x);
}

void add(int i, int val)  //将第i个元素增加val
{
	//i的祖先都增加val
	while(i <= n)
	{
		sum[i] += val;
		i += lowbit(i);   //将i的二进制未位1补为0得到其父亲
	}
}

int Sum(int i)   //求前i项的和
{
	int s = 0;
	//将前i项分段
	while(i > 0)
	{
		s += sum[i];
		i -= lowbit(i);  //去掉i的二进制最后一个1
	}
	return s;
}

int main()
{
	int t;
	char order[10];
	int a,b;
	cin>>t;
	for(int Case=1; Case<=t; Case++)
	{
		memset(sum,0,sizeof(sum));
		cout<<"Case "<<Case<<":"<<endl;
		cin>>n;
		for(int i=1; i<=n; i++)
		{
			cin>>num[i];
			add(i,num[i]);
		}
		while(1)
		{
			cin>>order;
			if(strcmp(order,"End") == 0)
			{
				break;
			}
			cin>>a>>b;
			if(strcmp(order,"Query") == 0)
			{
				cout<<Sum(b)-Sum(a-1)<<endl; 
			}
			if(strcmp(order,"Add") == 0)
			{
				add(a,b);
			}
			if(strcmp(order,"Sub") == 0)
			{
				add(a,-b);
			}
		}
	}
	return 0;
}
           

//线段树,hdu 1166,节点更新，区间求和

#include <iostream>
using namespace std;

const int MAXN = 50000 + 100;

struct treeNode
{
    int left;
    int right;
    int num;
}node[MAXN*3];

int num[MAXN];

int buildTree(int low, int top, int index) //功能：建树.父节点是左右子节点之和
{
    node[index].left = low;
    node[index].right = top;
    if (low == top)                    //是否已经递归到最低层
    {
        node[index].num = num[low];
        return node[index].num;
    }
    int mid = (low + top) / 2;
    node[index].num = buildTree(low,mid,index*2) + buildTree(mid+1,top,index*2+1);  //父节点为左右子节点之和
    return node[index].num;
}

void update(int k, int num, int index)
{
    node[index].num = node[index].num + num;  //每一个覆盖的区间都加上num
    if (node[index].left == node[index].right && node[index].left == k) //已经更新到最底层并且找到K点
    {
        return;
    }
    int mid = (node[index].left + node[index].right) / 2;
    if (k <= mid)                //如果k在左子树中
    {
        update(k,num,index*2);
    }
    else                          //如果k在右子树中
    {
        update(k,num,index*2+1);
    }
}

int search(int low, int top, int index)
{
    if (node[index].left == low && node[index].right == top)  //找到完全重合的区间,直接返回该值，即为本次搜索的最终结果
    {
        return node[index].num;
    }
    int mid = (node[index].left + node[index].right) / 2;
    if (top <= mid)      //搜索区间位于左子树
    {
        return search(low,top,index*2);
    }
    else if(low > mid)   //搜索区间位于右子树
    {
        return search(low,top,index*2+1);
    }
    else                  //搜索区间在左右子树间,即将区间分成2部分
    {
        return search(low,mid,index*2) + search(mid+1,top,index*2+1);
    }
}

int main()
{
    int t;
    int n;
    cin>>t;
    char command[10];
    int a,b;
    for (int Case=1; Case<=t; Case++)
    {
        cin>>n;
        for (int i=1; i<=n; i++)
        {
            cin>>num[i];
        }
        buildTree(1,n,1);
        cout<<"Case "<<Case<<":"<<endl;
        while (1)
        {
            cin>>command;
            if(command[0] == 'E')
            {
                break;
            }
            cin>>a>>b;
            if (command[0] == 'Q')
            {
                cout<<search(a,b,1)<<endl;
            }
            else if (command[0] == 'A')
            {
                update(a,b,1);
            }
            else if (command[0] == 'S')
            {
                update(a,-b,1);
            }
        }
    }
    return 0;
}