HDU 1754 樹狀數組 解法

要詢問一個數列的某區間的最大值，其中會更新數據。

這樣的題目使用樹狀數組是可以的，但是因為要牽涉到區間操作，故此還是線段樹比較好點。

不過使用樹狀數組也是可以的，就是查詢的時候麻煩點，注意計算，不要超出區間了。

看下面的query函數，這是主要的難點函數，其中的-1操作和這個判斷r - lowbit(r) >= l，都很蛋疼，一不小心就會出錯。

#include 
#include 
using namespace std;

class IHateIt_1754_2
{
	static const int SIZE = 200002;
	int *a, *c;//a為普通數組，c為樹狀數組
	inline int lowbit(int x)
	{
		return x & (-x);
	}

	void update(int i, int val, int len)
	{
		a[i] = val;
		while (i <= len)
		{
			c[i] = max(c[i], val);
			i += lowbit(i);
		}
	}

	int query(int l, int r)
	{
		int ans = a[r];//上邊界
		while (l != r)
		{
			for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r))
			{  
				ans = max(ans, c[r]);//注意計算區間，不要誇區間
			}  
			ans = max(ans, a[r]);  //下邊界
		}
		return ans;
	}

public:
	IHateIt_1754_2() : a((int*)malloc(sizeof(int)*SIZE)), 
		c((int*)malloc(sizeof(int)*SIZE))
	{
		int N, M;
		while (scanf("%d %d", &N, &M) != EOF)
		{
			fill(c, c+N+1, 0);
			for (int i = 1; i <= N; i++)
			{
				scanf("%d", &a[i]);
				update(i, a[i], N);
			}

			while (M--)
			{
				char op[2];
				int a, b;
				scanf("%s%d%d", op, &a, &b); 
				if (op[0] == 'U') update(a, b, N);
				else printf("%d\n", query(a, b));
			}
		}
	}

	~IHateIt_1754_2()
	{
		free(a), free(c);
	}
};