• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

现在有一个num的数组,构造了它的差数组diff。

int[]diff=new int[nums . length];

//差值数组的第一个元素是原始数组的第一个值

diff[0]=nums[0];

for(int I=1;inums.lengthi ){

diff=nums-num[i-1]

}

从上面的差分阵列构造可以推导出diff=nums-num[I-1]=diffnums[I-1];

因此,可以获得用于从差分阵列推导原始阵列的算法代码,如下所示:

Int[]RES=new Int[diff . length];

RES[0]=diff[0];

for(int I=0;ires .长度;i ){

RES=RES[I-1]diff

}

我们知道前缀和数组用于数组不变的场景,差分数组用于数组频繁增减的操作场景。

现在假设您将数组nums范围内的元素加3.j],如何用差分数组实现;

用公式RES=RES[I-1]diff;我们可以通过在diff上加3,在diff[j 1]上减3来实现

原理很简单。回想一下从diff数组反相nums数组的过程。diff=3意味着将nums的所有元素加3.],然后diff[j 1] -=3表示从nums[j 1]的所有元素中减去3.].那么,当组合在一起时,是否意味着将nums的所有元素加3.j]?

)

根据上述推论,可以构造出以下差分阵列的工具类。

阶级差异{

//差分阵列

private int[]diff;

//到达差分阵列

公共差异(int[] nums){

diff[0]=nums[0];

for(int I=1;inums.lengthi ){

diff=RES-RES[I-1];

}

}

/*将val(可以是负数)加到闭区间[i,j] */

public void increment(int i,int j,int val) {

diff=val;

//如果j 1等于diff.length,则意味着包括I在内的所有元素都加上val,所以不需要减去。

if (j 1 diff.length) {

diff[j 1]-=val;

}

}

//构造结果数组,对原数组进行nums运算后的数组

public int[] result(){

int[]RES=new int[diff . length];

//根据差数组构造结果数组

RES[0]=diff[0];

for(int I=1;I不同长度;i ) {

RES=RES[I-1]diff

}

返回res

}

}

Link to comment
Share on other sites