| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
poj 3468 线段树 存增量按照基本的存增量的思路,但是我在做查询的时候不修改数据结构;只有在查询的时候进行更新。始终通不过,求大牛帮忙。更新和查询代码如下
public static long getSum(long[][] st, int[] nums, int ss, int se) {
return getSumHelper(st, 0, 0, nums.length-1, nums, ss, se, 0l);
}
public static long getSumHelper(long[][] st, int stIndex, int ss, int se, int[] nums, int qs, int qe, long inc) {
if (stIndex < 0 || stIndex >= st.length) {
return 0l;
}
if (ss >= qs && se <= qe) {
return st[stIndex][0] + (st[stIndex][1]+inc) * (se-ss+1);
} else if (ss > qe || se < qs) {
return 0;
} else {
int mid = ss + (se - ss) / 2;
long ninc = st[stIndex][1] + inc;
long left = getSumHelper(st, (stIndex<<1) + 1, ss, mid, nums, qs, qe, ninc);
long right = getSumHelper(st, (stIndex<<1) + 2, mid+1, se, nums, qs, qe, ninc);
return left + right;
}
}
public static long updateST(long[][] st, int[] nums, int ss, int se, int c) {
return updateSTHelper(st, 0, 0, nums.length-1, nums, ss, se, 0, c);
}
public static long updateSTHelper(long[][] st, int stIndex, int ss, int se, int[] nums, int qs, int qe, long inc, int update) {
if (stIndex < 0 || stIndex >= st.length) {
return 0l;
}
st[stIndex][1] += inc;
if (ss >= qs && se <= qe) {
st[stIndex][1] += update;
return st[stIndex][0] + (se-ss+1) * st[stIndex][1];
} else if (ss > qe || se < qs) {
return st[stIndex][0] + st[stIndex][1] * (ss-se+1);
} else {
int mid = ss + (se - ss) / 2;
long left = updateSTHelper(st, (stIndex<<1)+1, ss, mid, nums, qs, qe, st[stIndex][1], update);
long right = updateSTHelper(st, (stIndex<<1)+2, mid+1, se, nums, qs, qe, st[stIndex][1], update);
st[stIndex][0] = left + right;
st[stIndex][1] = 0;
return st[stIndex][0];
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator