AOJ 0549 - A Traveler

Segment Tree問題．蟻本読みながらのんびりつくっていました．
何でnじゃ数値でないのかなあと思ってたら，st.n != nですね．
MAX_Nの見積りを誤ってました．要素は最上層が1個，次の層が2個，...，最下層(18層目)が2^17個(>100000．無駄にとっています)あります．
等比数列の和ですね．個でした．
よって，MAX_N = にすべきでした．
あと，剰余を出す問題も初めて解いた気がします．

#include<iostream>

const int MAX_N = 1 << 18, MOD = 100000;//ちょっと多いけど気にしないし(少なかったし)
class SegmentTree{
public:
	SegmentTree(int _n){
		n = 1;
		while(n < _n)n *= 2;
		std::fill(data, data+MAX_N, 0);
	}

	void update(int k, int i){
		k += n - 1;
		data[k] = i;
		while(k > 0){
			k = (k - 1) / 2;
			data[k] = (data[k*2+1] + data[k*2+2]) % MOD;
		}
	}

	int query(int a, int b, int k, int l, int r){
		if(r <= a || b <= l)return 0;

		if(a <= l && r <= b)return data[k];
		else{
			int cl = query(a, b, k*2+1, l, (l + r) / 2),
				cr = query(a, b, k*2+2, (l + r) / 2, r);
			return (cl + cr) % MOD;
		}
	}

	int getN(){
		return n;
	}

private:
	int n, data[MAX_N];
};

int main(){
	int n, m;
	std::cin >> n >> m;
	SegmentTree st(--n);

	for(int i=0;i<n;i++){
		int d;
		std::cin >> d;
		st.update(i, d);
	}

	int from = 0, to, res = 0;
	for(int i=0;i<m;i++){
		int a;
		std::cin >> a;
		to = from + a;
		int lower = std::min(from, to), upper = std::max(from, to);
		res = (res + st.query(lower, upper, 0, 0, st.getN())) % MOD;
		from = to;
	}

	std::cout << res << std::endl;
}