Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

poj 3468 线段树 存增量

Posted by manman511 at 2016-04-16 05:11:07
按照基本的存增量的思路,但是我在做查询的时候不修改数据结构;只有在查询的时候进行更新。始终通不过,求大牛帮忙。更新和查询代码如下


    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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator