| ||||||||||
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